首页 > 代码库 > [LeetCode] Maximum Product Subarray 连续数列最大积
[LeetCode] Maximum Product Subarray 连续数列最大积
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.
Hide Tags
Array Dynamic Programming 这个问题是给定一个数组，包括正负数和0，求连续子串数字最大的乘积，最容易动态规划，求出整个matrix<i,j> i-th 到 j-th 之间的数字之积，这样方法时间和空间都是O（n2），另一个比较技巧的方法，只需要O(n)时间和O(1)空间，考虑两个0 之间的数字：
0,a,b,c,d,e,f,g,h,0
如果a-h 之间的负数个数为偶数，那么结果就是a - h。
如果负数个数为奇数，假如为d， 那么考虑d 的左边，最大值为a-c，右边为e-h，因为两个部分中的负数个数为偶数。
这样在奇数情况下，只要d 去最靠近0的那个，便会有一部分是最大值。
这样只要从左遍历一次，再从右遍历一次便能找出。
逻辑：
- 判断输入个数。
- 设初始值，当前计算值curval = 1.
- 从左遍历数组。
- 如果遇到0，判断最大值（eg：-1，0，-2），curval =1，继续。
- 如果非0，那么curval 乘以该值，更新返回值。
- 从右遍历数组，重复4.5步，判断0就不要需要了。
1 #include <iostream> 2 using namespace std; 3 4 class Solution { 5 public: 6 int maxProduct(int A[], int n) { 7 if(n<2) return A[0]; 8 int retMax=A[0]; 9 int curval=1;10 for(int i=0;i<n;i++){11 if(A[i]==0){12 if(0>retMax) retMax=0;13 curval=1;14 continue;15 }16 curval*=A[i];17 if(curval>retMax) retMax=curval;18 }19 curval = 1;20 for(int i=n-1;i>=0;i--){21 if(A[i]==0){22 curval = 1;23 continue;24 }25 curval*= A[i];26 if(curval>retMax) retMax= curval;27 }28 return retMax;29 }30 };31 32 int main()33 {34 int a[]={-1,0,-2};35 Solution sol;36 cout<<sol.maxProduct(a,sizeof(a)/sizeof(int))<<endl;37 return 0;38 }
官方解法中结合了求最小值的解答，是一个标准的dp 过程，
f(k) ：0-th to k-th 的最大值
g(h)：0-th to k-th 的最小值
那么有：
f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )
[LeetCode] Maximum Product Subarray 连续数列最大积
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。