提交全系股票DP

xutao · xutao · commit 6b33b31274f5 · 2020-08-04T20:56:23.000+08:00
diff --git a/Week06/MaxProfit.java b/Week06/MaxProfit.java
@@ -0,0 +1,16 @@
+/**
+ * 121 股票最大和 =》见第二题的转化
+ */
+class MaxProfit {
+    public int maxProfit(int[] prices) {
+        int length = prices.length;
+        int dp_i_0 = 0;
+        int dp_i_1 = -Integer.MAX_VALUE;
+        for (int i = 0; i < length; i++) {
+            int temp = dp_i_0;
+            dp_i_0 = Math.max(temp, dp_i_1 + prices[i]);
+            dp_i_1 = Math.max(dp_i_1, prices[i]);
+        }
+        return dp_i_0;
+    }
+}
diff --git a/Week06/MaxProfit2.java b/Week06/MaxProfit2.java
@@ -0,0 +1,52 @@
+/**
+ * 122 股票最大和II 。可以无限交易
+ */
+class MaxProfit2 {
+    public int maxProfit(int[] prices) {
+        int length = prices.length;
+        if (length == 0) {
+            return 0;
+        }
+        int dp[][] = new int[length + 1][2];
+        dp[1][0] = 0;
+        dp[1][1] = -prices[0];
+        for (int i = 2; i <= length; i++) {
+            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
+            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
+        }
+        return dp[length][0];
+    }
+
+
+    /**
+     * 使用滑动数组解决问题
+     */
+    public int maxProfit2(int[] prices) {
+        int length = prices.length;
+        int dp[][] = new int[length + 1][2];
+        dp[0][1] = -Integer.MAX_VALUE;
+        for (int i = 1; i <= length; i++) {
+            int temp = dp[i - 1][0];
+            dp[i][0] = Math.max(temp, dp[i - 1][1] + prices[i - 1]);
+            dp[i][1] = Math.max(dp[i - 1][1], temp - prices[i - 1]);
+        }
+        return dp[length][0];
+    }
+
+
+    /**
+     * 使用最终O(1)的空间解决问题
+     */
+    public int maxProfit3(int[] prices) {
+        int length = prices.length;
+        int dp_i_0 = 0;
+        int dp_i_1 = -Integer.MAX_VALUE;
+        for (int i = 0; i < length; i++) {
+            int temp = dp_i_0;
+            dp_i_0 = Math.max(temp, dp_i_1 + prices[i]);
+            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
+        }
+        return dp_i_0;
+    }
+
+}
diff --git a/Week06/MaxProfit3.java b/Week06/MaxProfit3.java
@@ -0,0 +1,17 @@
+/**
+ * 123 股票最大和 ，含1回合cd
+ */
+class MaxProfit3 {
+    public int maxProfit(int[] prices) {
+        int length = prices.length;
+        int dp_i_0 = 0, dp_pre_0 = 0;
+        int dp_i_1 = Integer.MIN_VALUE;
+        for (int i = 0; i < length; i++) {
+            int temp = dp_i_0;
+            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
+            dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
+            dp_pre_0 = temp;
+        }
+        return dp_i_0;
+    }
+}
diff --git a/Week06/MaxProfit4.java b/Week06/MaxProfit4.java
@@ -0,0 +1,16 @@
+/**
+ * 714 股票最大和 含手续费
+ */
+class MaxProfit4 {
+    public int maxProfit(int[] prices, int fee) {
+        int length = prices.length;
+        int dp_i_0 = 0;
+        int dp_i_1 = Integer.MIN_VALUE;
+        for (int i = 0; i < length; i++) {
+            int temp = dp_i_0;
+            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
+            dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
+        }
+        return dp_i_0;
+    }
+}
diff --git a/Week06/MaxProfit5.java b/Week06/MaxProfit5.java
@@ -0,0 +1,17 @@
+/**
+ * k=2 习题123，最多交易2笔
+ */
+class MaxProfit5 {
+    public int maxProfit(int[] prices, int fee) {
+        int length = prices.length;
+        int dp_i_1_0 = 0, dp_i_2_0 = 0;
+        int dp_i_1_1 = Integer.MIN_VALUE, dp_i_2_1 = Integer.MIN_VALUE;
+        for (int i = 0; i < length; i++) {
+            dp_i_2_0 = Math.max(dp_i_2_0, dp_i_2_1 + prices[i]);
+            dp_i_2_1 = Math.max(dp_i_2_1, dp_i_1_0 - prices[i]);
+            dp_i_1_0 = Math.max(dp_i_1_0, dp_i_1_1 + prices[i]);
+            dp_i_1_1 = Math.max(dp_i_1_1, -prices[i]);
+        }
+        return dp_i_2_0;
+    }
+}
diff --git a/Week06/MaxProfit6.java b/Week06/MaxProfit6.java
@@ -0,0 +1,45 @@
+/**
+ * k=any 188交易股票 暂时超时
+ */
+class MaxProfit6 {
+    public int maxProfit(int k, int[] prices) {
+        int length = prices.length;
+        if (k > length / 2) {
+            return maxProfitInf(prices, length);
+        } else {
+            return maxProfitAny(prices, k, length);
+        }
+    }
+
+    public int maxProfitAny(int[] prices, int k, int length) {
+        int dp[][][] = new int[length ][k+1][2];
+        for (int i = 0; i <= length; i++) {
+            for (int j = k; j >= 1; k--) {
+                if (i == 0) {
+                    /** 处理基础值*/
+                    dp[i][j][0] = 0;
+                    dp[i][j][1] = Integer.MIN_VALUE;
+                    continue;
+                }
+                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
+                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
+            }
+        }
+        return dp[length-1][k][0];
+    }
+
+    /**
+     * 使用最终O(1)的空间解决问题
+     */
+    public int maxProfitInf(int[] prices, int length) {
+        int dp_i_0 = 0;
+        int dp_i_1 = -Integer.MAX_VALUE;
+        for (int i = 0; i < length; i++) {
+            int temp = dp_i_0;
+            dp_i_0 = Math.max(temp, dp_i_1 + prices[i]);
+            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
+        }
+        return dp_i_0;
+    }
+
+}
diff --git a/Week06/MaxSubArray.java b/Week06/MaxSubArray.java
@@ -0,0 +1,17 @@
+
+/**
+ * 最长子序列和 53
+ */
+class MaxSubArray {
+    public int maxSubArray(int[] nums) {
+        int max = nums[0];
+        for (int i = 1; i < nums.length; i++) {
+            int prev = nums[i - 1] > 0 ? nums[i - 1] : 0;
+            nums[i] += prev;
+            if (nums[i] > max) {
+                max = nums[i];
+            }
+        }
+        return max;
+    }
+}
