LeetCode Maximum Product Subarray 最大子序列积

题意:给一个size大于0的序列,求最大的连续子序列之积。(有正数,负数,0)

思路:正确分析这三种数。0把不同的可能为答案的子序列给隔开了,所以其实可以以0为分隔线将他们拆成多个序列来进行求积,这样就没有0了。

  接着是负数,负数如果遇到一个负数,可能反而比那个正数要大,所以正负数都要保存,遍历一次即可。在奇数个负数时,其实可能的只有2种:(1)包含最前面一个负数的序列(2)包含最后面一个负数的序列(当然不包含最前面1个,同理(1)也是)。

 class Solution {
public:
int maxProduct(vector<int>& nums) {
int a=, b=, res=nums[];
for(int i=; i<nums.size(); i++)
{
int t=a;
a=max(b*nums[i],a*nums[i]); //a保存大的
b=min(t*nums[i],b*nums[i]); //b保存小的
res=max(res, a);
//if(a<=0) a=1; //必须保证a大于0
if(b>=) b=; //必须保证b小于0。为了不改变原值,只能为1。
}
return res;
}
};

AC代码

上一篇:【poj2154】Color Polya定理+欧拉函数


下一篇:Python爬虫利器二之Beautiful Soup的用法