最大连续子序列乘积

http://blog.csdn.net/wzy_1988/article/details/9319897

最大连续子序列乘积和最大连续子序列和不同，这里先回忆一下最大连续子序列和的最优解结构：

最大连续子序列和

我们用sum[i]来表示以arr[i]结尾的最大连续子序列和，则状态转移方程为：

最大连续子序列乘积

考虑存在负数的情况（ps：负负会得正），因此我们用两个辅助数组，max[i]和min[i],max[i]来表示以arr[i]结尾的最大连续子序列乘积，min[i]来表示以arr[i]结尾的最小连续子序列乘积，因此状态转移方程为：

and

有了状态转移方程，dp代码就很容易实现了

1. int main(void)  
2. {  
3.     int i, n;  
4.     double *arr, *max, *min, res;  
5.    
6.     while (scanf("%d", &n) != EOF) {  
7.         arr = (double *)malloc(sizeof(double) * n);  
8.         max = (double *)malloc(sizeof(double) * n);  
9.         min = (double *)malloc(sizeof(double) * n);  
10.         for (i = 0; i < n; i ++)  
11.             scanf("%lf", arr + i);  
12.    
13.         // 动态规划求最大连续子序列乘积  
14.         max[0] = min[0] = res = arr[0];  
15.         for (i = 1; i < n; i ++) {  
16.             max[i] = maxNumInThree(arr[i], max[i - 1] * arr[i], min[i - 1] * arr[i]);  
17.             min[i] = minNumInThree(arr[i], max[i - 1] * arr[i], min[i - 1] * arr[i]);  
18.             if (max[i] > res)  
19.                 res = max[i];  
20.         }  
21.    
22.         if (res >= 0) {  
23.             // 判断是否为浮点数  
24.             if ((res - (int)res) == 0)  
25.                 printf("%d\n", (int)res);  
26.             else  
27.                 printf("%.2lf\n", res);  
28.         } else {  
29.             printf("-1\n");  
30.         }  
31.    
32.         free(arr);  
33.     }  
34.    
35.     return 0;  
36. }