[LeetCode]152. Maximum Product Subarray

Problem

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

1
2
3
4
5
6
7
8
9
10
Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Solution

Analysis

自己写的时候,没有考虑完整,陷入困境. 我原以为,使用一维动态规划dp[i],表示包括i的子数组的最大内积, 转移的时候, 只需要判断当前数和上一个数符号是否一致,如果一致,dp[i] = dp[i-1]*nums[i]. 但实际上这种方法是错误的, 因为不能考虑到[-1, 2, -9]这种情况, 如果用上面的方法,返回2, 正确结果是18. 主要原因就在于负负得正, 而负号结果又不在一块,导致判断条件出错. 后来我又想,状态转移时,从后往前遍历,直到找到符号相同的,然后再更新结果, 但是这种情况主要应对的是负负得正的情况, 更复杂了.解不出来sad…

Google. 参考方法是使用两个动态规划矩阵.[以前从来没见过,开眼了]. dp_min[i], dp_max[j], 分别记录包含当前数字在内的子数组内积的最小值和最大值. 状态转移时, dp_max[i]它的结果可能来源于nums[i]dp_min[i-1],nums[i]dp_min[j-1],或者是nums[i], 主要依据当前值的符号, 如果是负数,可能结果就是乘以dp_min[i-1]. 因为当前值是负数时,乘以之前的子数组内积最大值,就变成了最小值; 同理,乘以最小值,就变成了最大值.

dp_max(k) = max( dp_max(k-1) A[k], A[k], dp_min(k-1) A[k] ) dp_min(k) = min( dp_max(k-1) A[k], A[k], dp_min(k-1) A[k] )

而所求的最大值,只可能来源于dp_max[k]和当前值nums[k].

Code

节省空间. 实际上每个状态转移时,仅仅和上一个状态有关,所以空间复杂度可以变成O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int maxProduct(vector<int>& nums) {
// 没想到会用两个动态规划数组
if(nums.empty()) return 0;

int result = nums[0], mn = nums[0], mx = nums[0], size = nums.size();

for (int i=1; i< size; ++i){
int tmax = mx, tmin = mn;
mx = max(max(nums[i], tmax*nums[i]), tmin*nums[i]);
mn = min(min(nums[i], tmax*nums[i]), tmin*nums[i]);

result = max(mx, result);
}

return result;
}
};

References

https://www.cnblogs.com/grandyang/p/4028713.html

您的支持就是我更新的最大动力!谢谢!