力扣152
https://leetcode-cn.com/problems/maximum-product-subarray/
这题不是普通的动态规划题，借助了最大最小两个数组来进行动态规划
动态规划解法可以参考官方题解
https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
在评论区看到一个很妙的思路，动态规划的关键在哪里？关键就在于
只要相乘不为0，绝对值就会增大。如果数组的数是负数，那么会导致最大的变最小的，最小的变最大的，最大最小保存起来交换即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int maxProduct2(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for(int i=0; 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]);
max = Math.max(max, imax);
}
return max;
}
|
太强了，这辈子想不出了…
不过这道题可以有一个更加容易思考的解法：
记录一个当前乘积product，一个当前最大max
1如果有0，则会以0为分界点，将product重置为1重新计算
2如果没有0，分为两种情况：
2.1负数为偶数，一直乘到底
2.2负数为奇数，从左边开始乘到最后一个负数前有一个最大值，从右边开始乘也有一个最大值，比较即可
明白了这一点后可以简化：
2.2中所说“最后一个负数前”其实不需要考虑，直接乘到底，因为我们记录了max，就算乘到底也不会比max大（负数<正数）
2.1可以包含在2.2中，只不过左右两次结果一样罢了
1可以包含在2.2中，只需要判断当前是否为0重置product即可
所以代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int maxProduct(int[] nums) {
int product = 1;
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
product *= nums[i];
max = Math.max(max, product);
if (nums[i] == 0) product = 1;
}
product = 1;
for (int i = nums.length - 1; i >= 0; i--) {
product *= nums[i];
max = Math.max(max, product);
if (nums[i] == 0) product = 1;
}
return max;
}
|
其他动态规划的题目可以点击这里