动态规划问题
记 n_max [i] 为以 nums[i] 为结尾的子序列的最大乘积
记 n_min [i] 为以 nums[i] 为结尾的子序列的最小乘积
则
n_max[i+1] = max( n_max[i]nums[i],n_min[i]nums[i],nums[i] )
n_min [i+1] = min( n_max[i]nums[i],n_min[i]nums[i],nums[i] )
最后的答案 res = max( n_max[i] ) ( 0 <= i < numsSize )
生成一个新的状态只会用到前一个状态，所以只保存前一个状态就好。
#define max2(a,b) ((a)>(b)?(a):(b))
#define min2(a,b) ((a)<(b)?(a):(b))
#define max3(a,b,c) max2(max2(a,b),max2(b,c))
#define min3(a,b,c) min2(min2(a,b),min2(b,c))
int maxProduct(int* nums, int numsSize) {
long long n_max = nums[0];
long long n_min = nums[0];
long long res = nums[0];
for( int i = 1;i<numsSize;i++ ){
long long old_max = n_max;
n_max = max3( n_max*nums[i],n_min*nums[i],nums[i] );
n_min = min3( old_max*nums[i],n_min*nums[i],nums[i] );
res = max2(res,n_max);
}
return (int)res;
}
