LeetCode 152. Maximum Product Subarray

动态规划问题

记 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;
}