leetcode题解 problem 152 Maximum Product Subarray
Tags: leetcode
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的变形，把求和改成求积了。且有负数。
设DP[i]是以i位置元素为终点的子序列的乘积，那么DP[i]的最大值就是我们要的解。
DP[i] = max( DP[i - 1] * nums[i], nums[i] )
上面的方程是错的，因为没有考虑到负数的情况，比如数组[-10,5,-10]，DP[0] = -10, DP[1] = 5, DP[2] =-10，最大乘积是5。 但实际上最大乘积是 -10 * 5 ＊ (-10) = 500。
正确的方程是，记录2个DP数组，一个记乘积最大值，一个记乘积最小值，然后综合2个DP数组的结果，就可以得到真正的最大值。
1 DP_max[i] = max( DP_min[i - 1] * nums[i], DP_max[i - 1] * nums[i], nums[i])
2
3 DP_min[i] = min( DP_min[i - 1] * nums[i], DP_max[i - 1] * nums[i], nums[i])按这个方程组来做的话，需要O(n)的空间，考虑到题目只要求输出最大值，那么可以优化到O(1)的空间消耗。
原理就是，DP_*[i]只和上一个状态以及当前的值有关，那么只需要保存上一个状态的结果，就足够求最大乘积了。
下面是我的代码：（runtime 8 ms）
1 int maxProduct(vector<int>& nums) {
2 if (nums.size() == 0)
3 return 0;
4 int dp_pre_min = nums[0];
5 int dp_pre_max = nums[0];
6 int dp_max = dp_pre_max;
7 for (int i = 1, len = nums.size(); i < len; ++i){
8 int dp_cur_max = max( max(nums[i], dp_pre_max*nums[i]), dp_pre_min*nums[i]);
9 int dp_cur_min = min( min(nums[i], dp_pre_max*nums[i]), dp_pre_min*nums[i]);
10 if (dp_max < dp_cur_max)
11 dp_max = dp_cur_max;
12 dp_pre_max = dp_cur_max;
13 dp_pre_min = dp_cur_min;
14 }
15 return dp_max;
16 }
(未经授权禁止转载)
Written on July 6, 2015
博主将十分感谢对本文章的任意金额的打赏^_^
