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.
找数字连续最大乘积子序列。
思路：这个麻烦在有负数和0，我的方法，如果有0，一切都设为初始值。
对于两个0之间的数若有奇数个负数，那则有两种情况，第一种是不要第一个负数和之前的值，第二种是不要最后一个负数和之后的值，用negtiveFront和negtiveBack表示。没有负数就是不要第一个负数和之前的值的情况。
int maxProduct(int A[], int n) {
if(n == )
return ;
int MaxAns = A[];
int negtiveFront = (A[] == ) ? : A[];
int negtiveBack = (A[] < ) ? : ;
for(int i = ; i < n; i++)
{
if(A[i] == )
{
MaxAns = (MaxAns > ) ? MaxAns : ;
negtiveFront = ;
negtiveBack = ;
}
else if(A[i] < )
{
negtiveFront *= A[i];
MaxAns = max(negtiveFront, MaxAns);
if(negtiveBack == )
{
negtiveBack = ;
}
else
{
negtiveBack *= A[i];
MaxAns = max(negtiveBack, MaxAns);
}
}
else
{
negtiveFront *= A[i];
negtiveBack *= A[i];
MaxAns = max(negtiveFront, MaxAns);
if(negtiveBack > )
{
MaxAns = max(negtiveBack, MaxAns);
}
}
}
return MaxAns;
}
答案的思路：同时维护包括当前数字A[k]的最大值f(k)和最小值g(k)
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] )
再用一个变量Ans存储所有f(k)中最大的数字就可以了
int maxProduct2(int A[], int n) {
if(n == )
return ;
int MaxAns = A[]; //包括当前A【i】的连续最大乘积
int MinAns = A[]; //包括当前A【i】的连续最小乘积
int MaxSoFar = A[]; //整个数组的最大乘积
for(int i = ; i < n; i++)
{
int MaxAnsTmp = MaxAns;
int MinAnsTmp = MinAns;
MaxAns = max(MaxAnsTmp * A[i], max(MinAnsTmp * A[i], A[i]));
MinAns = min(MinAnsTmp * A[i], min(MaxAnsTmp * A[i], A[i]));
MaxSoFar = max(MaxSoFar, MaxAns);
}
return MaxSoFar;
}