动态规划：152.乘积最大子数组、279.完全平方数

linwt · linwt · commit 6725a09cbf19 · 2022-03-08T22:55:08.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -37,6 +37,7 @@
 141. 环形链表
 144. 二叉树的前序遍历
 145. 二叉树的后序遍历
+152. 乘积最大子数组
 155. 最小栈
 160. 相交链表
 169. 多数元素
@@ -46,6 +47,7 @@
 226. 翻转二叉树
 234. 回文链表
 236. 二叉树的最近公共祖先
+279. 完全平方数
 283. 移动零
 300. 最长上升子序列
 303. 区域和检索 - 数组不可变
diff --git a/leetcode_Java/Solution0152.java b/leetcode_Java/Solution0152.java
@@ -0,0 +1,61 @@
+// 152. 乘积最大子数组
+
+
+/*
+1、res记录子数组最大乘积，imax表示以nums[i]结尾的子数组最大乘积，imin表示以nums[i]结尾的子数组最小乘积
+2、遍历数据，计算当前最大值，不断更新res
+3、由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，当负数出现时则imax与imin进行交换再进行下一步计算
+ */
+class Solution {
+    public int maxProduct(int[] nums) {
+        int res = nums[0], imax = 1, imin = 1;
+        for (int i = 1; i < nums.length; i++) {
+            if (nums[i] < 0) {
+                int temp = imax;
+                imax = imin;
+                imin = temp;
+            }
+            imax = Math.max(imax * nums[i], nums[i]);
+            imin = Math.min(imin * nums[i], nums[i]);
+            res = Math.max(res, imax);
+        }
+        return res;
+    }
+}
+
+
+/*
+动态规划：
+1、dpMax[i]表示以i位置结尾的子数组最大乘积，dpMin[i]表示以i位置结尾的子数组最小乘积
+ */
+class Solution {
+    public int maxProduct(int[] nums) {
+        int res;
+        int[] dpMax = new int[n];
+        int[] dpMin = new int[n];
+        res = dpMax[0] = dpMin[0] = nums[0];
+        for (int i = 1; i < n; i++) {
+            dpMax[i] = Math.max(nums[i], Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
+            dpMin[i] = Math.min(nums[i], Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
+            res = Math.max(res, dpMax[i]);
+        }
+        return res;
+    }
+}
+
+
+/*
+优化空间，使用变量替代dp数组
+ */
+class Solution {
+    public int maxProduct(int[] nums) {
+        int res = nums[0], imax = 1, imin = 1;
+        for (int i = 0; i < nums.length; i++) {
+            int imaxOld = imax, iminOld = imin;
+            imax = Math.max(nums[i], Math.max(imaxOld * nums[i], iminOld * nums[i]));
+            imin = Math.min(nums[i], Math.min(imaxOld * nums[i], iminOld * nums[i]));
+            res = Math.max(res, imax);
+        }
+        return res;
+    }
+}
diff --git a/leetcode_Java/Solution0279.java b/leetcode_Java/Solution0279.java
@@ -0,0 +1,24 @@
+// 279. 完全平方数
+
+
+/*
+动态规划：
+1、dp[i]表示和为i的完全平方数的最少数量
+2、遍历1-n，填充dp[i]元素
+3、初始化 dp[i] = i，表示最后情况全部由1相加，数量为i
+4、状态转移方程：dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
+5、j*j 是一个完全平方数，i-j*j 表示减去一个完全平方数的值，dp[i-j*j] 表示和为 i-j*j 完全平方数的最少数量，dp[i-j*j] + 1 表示和为i的完全平方数的数量
+6、构成i有多个完全平方数相加，所以遍历j，每次减去一个j*j的完全平方数，由旧状态加1直接得到当前值数量，比较得到最少数量
+ */
+class Solution {
+    public int numSquares(int n) {
+        int[] dp = new int[n + 1];
+        for (int i = 1; i <= n; i++) {
+            dp[i] = i;
+            for (int j = 1; j * j <= i; j++) {
+                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
+            }
+        }
+        return dp[n];
+    }
+}
