題目描述：給一個浮點數序列，取最大乘積連續子串的值，例如 -2.5，4，0，3，0.5，8，-1，則取出的最大乘積連續子串為3，0.5，8。也就是說，上述數組中，3 0.5 8這3個數的乘積3*0.5*8=12是最大的，而且是連續的。

提醒：此最大乘積連續子串與最大乘積子序列不同，請勿混淆，前者子串要求連續，后者子序列不要求連續。也就是說：最長公共子串（Longest CommonSubstring）和最長公共子序列（LongestCommon Subsequence，LCS）的區別：

    子串（Substring）是串的一個連續的部分，子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；
    更簡略地說，前者（子串）的字符的位置必須連續，后者（子序列LCS）則不必。比如字符串“ acdfg ”同“ akdfc ”的最長公共子串為“ df ”，而它們的最長公共子序列LCS是“ adf ”，LCS可以使用動態規劃法解決。

解答：

    解法一、窮舉，所有的計算組合：
    或許，讀者初看此題，自然會想到最大乘積子序列問題類似于最大子數組和問題：http://blog.csdn.net/v_JULY_v/article/details/6444021，可能立馬會想到用最簡單粗暴的方式：兩個for循環直接輪詢。

    解法二、雖說類似于最大子數組和問題，但實際上具體處理起來諸多不同。為什么呢，因為乘積子序列中有正有負也還可能有0。我們可以把問題簡化成這樣：數組中找一個子序列，使得它的乘積最大；同時找一個子序列，使得它的乘積最?。ㄘ摂档那闆r）。因為雖然我們只要一個最大積，但由于負數的存在，我們同時找這兩個乘積做起來反而方便。也就是說，不但記錄最大乘積，也要記錄最小乘積。So，我們讓maxCurrent表示當前最大乘積的candidate，minCurrent反之，表示當前最小乘積的candidate，而maxProduct則記錄到目前為止所有最大乘積candidates的最大值。（以上用candidate這個詞是因為只是可能成為新一輪的最大/最小乘積）由于空集的乘積定義為1，在搜索數組前，maxCurrent，minCurrent，maxProduct都賦為1。
假設在任何時刻你已經有了maxCurrent和minCurrent這兩個最大/最小乘積的candidates，新讀入數組的元素x(i)后，新的最大乘積candidate只可能是maxCurrent或者minCurrent與x(i)的乘積中的較大者，如果x(i)<0導致maxCurrent<minCurrent，需要交換這兩個candidates的值。當任何時候maxCurrent<1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent為1，類似的可以更新minCurrent。任何時候maxCurrent如果比最好的maxProduct大，更新maxProduct。

    解法三、本題除了上述類似最大子數組和的解法，也可以直接用動態規劃求解（其實，上述的解法一本質上也是動態規劃，只是解題所表現出來的具體形式與接下來的解法二不同罷了。這個不同就在于下面的解法二會寫出動態規劃問題中經典常見的DP方程，而解法一是直接求解）。具體解法如下：
    假設數組為a[]，直接利用動歸來求解，考慮到可能存在負數的情況，我們用Max來表示以a結尾的最大連續子串的乘積值，用Min表示以a結尾的最小的子串的乘積值，那么狀態轉移方程為：
       Max=max{a, Max[i-1]*a, Min[i-1]*a};
       Min=min{a, Max[i-1]*a, Min[i-1]*a};
 初始狀態為Max[1]=Min[1]=a[1]。

下面來看一道具體的ACM題目
 題目

    題目描述： 
    給定一個浮點數序列（可能有正數、0和負數），求出一個最大的連續子序列乘積。 
    輸入： 
    輸入可能包含多個測試樣例。 
    每個測試樣例的第一行僅包含正整數 n（n<=100000），表示浮點數序列的個數。 
    第二行輸入n個浮點數用空格分隔。 
    輸入數據保證所有數字乘積在雙精度浮點數表示的范圍內。 
    輸出： 
    對應每個測試案例，輸出序列中最大的連續子序列乘積，若乘積為浮點數請保留2位小數，如果最大乘積為負數，輸出-1。 
    樣例輸入：  

  7   -2.5 4 0 3 0.5 8 -1   5   -3.2 5 -1.6 1 2.5   5   -1.1 2.2 -1.1 3.3 -1.1 

    樣例輸出：  

  12   64   8.78 

思路
最大連續子序列乘積和最大連續子序列和不同，這里先回憶一下最大連續子序列和的最優解結構：

最大連續子序列和
我們用sum[i]來表示以arr[i]結尾的最大連續子序列和，則狀態轉移方程為：

最大連續子序列乘積
考慮存在負數的情況（ps：負負會得正），因此我們用兩個輔助數組，max[i]和min[i],max[i]來表示以arr[i]結尾的最大連續子序列乘積，min[i]來表示以arr[i]結尾的最小連續子序列乘積，因此狀態轉移方程為：

and

有了狀態轉移方程，dp代碼就很容易實現了，看到這里還不理解的同學，我建議你多花點時間用在算法學習上吧！

AC代碼

 #include <stdio.h>   #include <stdlib.h>       double maxNumInThree(double a, double b, double c)   {     double max;     max = (a > b) ? a : b;     max = (max > c) ? max : c;         return max;   }       double minNumInThree(double a, double b, double c)   {     double min;     min = (a < b) ? a : b;     min = (min < c) ? min : c;         return min;   }           int main(void)   {     int i, n;     double *arr, *max, *min, res;         while (scanf("%d", &n) != EOF) {       arr = (double *)malloc(sizeof(double) * n);       max = (double *)malloc(sizeof(double) * n);       min = (double *)malloc(sizeof(double) * n);       for (i = 0; i < n; i ++)         scanf("%lf", arr + i);           // 動態規劃求最大連續子序列乘積       max[0] = min[0] = res = arr[0];       for (i = 1; i < n; i ++) {         max[i] = maxNumInThree(arr[i], max[i - 1] * arr[i], min[i - 1] * arr[i]);         min[i] = minNumInThree(arr[i], max[i - 1] * arr[i], min[i - 1] * arr[i]);         if (max[i] > res)           res = max[i];       }           if (res >= 0) {         // 判斷是否為浮點數         if ((res - (int)res) == 0)           printf("%d/n", (int)res);         else           printf("%.2lf/n", res);       } else {         printf("-1/n");       }           free(arr);     }         return 0;   } 

       
    /**************************************************************
        Problem: 1501
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:110 ms
        Memory:4964 kb
    ****************************************************************/