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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
f(k) = Largest product subarray, from index 0 up to k, but must multiply A[k].
g(k) = Smallest product subarray, from index 0 up to k, but must multiply A[k].
在f(k)和g(k)中,
f(k)是指从0~k,最后乘以A[k]的最大值,
g(k)是指从0~k,最后乘以A[k]的最小值.
所以这也是为什么f(k),g(k)并不是全局的最大值和最小值,之所以一定要乘上A[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] )
在递推公式中,如果f(k)为A[k],表示从k重新开始。
比如{2,3,-2,4},k=2时,f(k)=-2,表示从-2处重新开始计算最大值。
*/
class Solution {
public:
int maxProduct(int A[], int n) {
int min_tmp = A[0];
int max_tmp = A[0];
int result = max_tmp;
for (int i = 1; i < n; i++) {
int a = min_tmp * A[i];
int b = max_tmp * A[i];
min_tmp = min(min(a, b), A[i]);
max_tmp = max(max(a, b), A[i]);
result = max(result, max_tmp);
}
return result;
}
};