Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
这道题的要求是求数组中积最大子数组。
积最大子数组，类似于Maximum Subarray， 只不过这个积最大要比和最大麻烦一点点。。。
同样采用动态规划，不过在维护当前最大值的时候cur_max[i]（以nums[i]结束的子数组的乘积最大值），还需要维护当前最小值cur_min[i]（以nums[i]结束的子数组的乘积最小值），因为如果最小值乘以下一个负数的话，就是最大值了。那么cur_max和cur_min的递推公式为：
- cur_max[i+1] = max(cur_max[i]∗nums[i+1], nums[i+1], cur_min[i]∗nums[i])；
- cur_min[i+1] = min(cur_min[i]∗nums[i+1], nums[i+1], cur_max[i]∗nums[i])。
cur_max[i+1]的递推公式就是在之前Maximum Subarray的递推公式中加入cur_min[i]*nums[i]，因为最小值乘以一个负数有可能变成最大值。cur_min[i+1]的递推公式则相反（看起来相反，比较的三部分实则相同）。当然全局最大值仍旧是res = max(res, cur_max)。
时间复杂度：O(n)
空间复杂度：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.size() == 0)
return 0;
int cur_max = nums[0], cur_min = nums[0], res = nums[0];
for(int i = 1; i < nums.size(); ++ i)
{
int temp_max = cur_max, temp_min = cur_min;
cur_max = max(max(temp_max * nums[i], nums[i]), temp_min * nums[i]);
cur_min = min(min(temp_min * nums[i], nums[i]), temp_max * nums[i]);
res = max(res, cur_max);
}
return res;
}
};
当然，在发现下一个数字nums[i+1]为负数的时候，如果乘以这个负数，最大值将会成为最小值，最小值将会成为最大值，因此，可以交换cur_max[i]和cur_min[i]的数值，再与这个负数相乘。因此递推公式为：
- cur_max[i+1] = max(cur_max[i]∗nums[i+1], nums[i+1])；
- cur_min[i+1] = min(cur_min[i]∗nums[i+1], nums[i+1])。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
public:
int maxProduct(vector<int>& nums)
{
if(nums.size() == 0)
return 0;
int cur_max = nums[0], cur_min = nums[0], res = nums[0];
for(int i = 1; i < nums.size(); ++ i)
{
if(nums[i] < 0)
swap(cur_max, cur_min);
cur_max = max(cur_max * nums[i], nums[i]);
cur_min = min(cur_min * nums[i], nums[i]);
res = max(res, cur_max);
}
return res;
}
};