动态规划问题 记 n_max [i] 为以 n ms[i] 为结尾的子序列的最大乘积 记 n_min [i] 为以 n ms[i] 为结尾的子序列的最小乘积 则 n_max[i+1] = max( n_max[i]n ms[i],n_min[i]n ms[i],n ms[i] ) n_min [i+1] = min( n_max[i]n ms[i],n_min[i]n ms[i],n ms[i] ) 最后的答案 res = max( n_max[i] ) ( 0 = i  n mssize ) 生成一个新的状态只会用到前一个状态,所以只保存前一个状态就好. #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 maxprod ct(int* n ms, int n mssize) { long long n_max = n ms[0]; long long n_min = n ms[0]; long long res = n ms[0]; for( int i = 1;in mssize;i ){ long long old_max = n_max; n_max = max3( n_max*n ms[i],n_min*n ms[i],n ms[i] ); n_min = min3( old_max*n ms[i],n_min*n ms[i],n ms[i] ); res = max2(res,n_max);