http://blog.csdn.net/v_july_v/article/details/8701148
假设数组为a[],直接利用动归来求解,考虑到可能存在负数的情况,我们用Max来表示以a结尾的最大连续子串的乘积值,用Min表示以a结尾的最小的子串的乘积值,那么状态转移方程为:
Max=max{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};
Min=min{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};
初始状态为Max[0]=Min[0]=a[0]。
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProduct(int A[], int n) {
int *maxArray = new int[n];
int *minArray = new int[n];
maxArray[] = minArray[] = A[];
int result=maxArray[];
for (int i = ; i < n; i++)
{
maxArray[i] = max(max(maxArray[i-]*A[i],minArray[i-]*A[i]),A[i]);
minArray[i] = min(min(maxArray[i-]*A[i],minArray[i-]*A[i]),A[i]);
result = max(result,maxArray[i]);
}
return result;
}
};
int main()
{
Solution s;
int n = ;
int a[] = {,,-,};
cout << s.maxProduct(a,)<<endl;
return ;
}
==============================================================================================
LinkedIn - Maximum Sum/Product Subarray
Maximum Sum Subarray是leetcode原题,跟Gas Station的想法几乎一模一样。解答中用到的结论需要用数学简单地证明一下。
1
2
3
4
5
6
7
8
9
10
11
12
|
public int maxSubArray( int [] A) {
int sum = 0 ;
int max = Integer.MIN_VALUE;
for ( int i = 0 ; i < A.length; i++) {
sum += A[i];
if (sum > max)
max = sum;
if (sum < 0 )
sum = 0 ;
}
return max;
} |
Maximum Product Subarray其实只需要不断地记录两个值,max和min。max是到当前为止最大的正product,min是到当前为止最小的负product,或者1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public int maxProduct( int [] A) {
int x = 1 ;
int max = 1 ;
int min = 1 ;
for ( int i = 0 ; i < A.length; i++) {
if (A[i] == 0 ) {
max = 1 ;
min = 1 ;
} else if (A[i] > 0 ) {
max = max * A[i];
min = Math.min(min * A[i], 1 );
} else {
int temp = max;
max = Math.max(min * A[i], 1 );
min = temp * A[i];
}
if (max > x)
x = max;
}
return x;
} |
http://shepherdyuan.wordpress.com/2014/07/23/linkedin-maximum-sumproduct-subarray/