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

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

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

解答：

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

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

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

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

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

思路
最大連續(xù)子序列乘積和最大連續(xù)子序列和不同，這里先回憶一下最大連續(xù)子序列和的最優(yōu)解結(jié)構(gòu)：

最大連續(xù)子序列和
我們用sum[i]來表示以arr[i]結(jié)尾的最大連續(xù)子序列和，則狀態(tài)轉(zhuǎn)移方程為：

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

and

有了狀態(tài)轉(zhuǎn)移方程，dp代碼就很容易實現(xiàn)了，看到這里還不理解的同學(xué)，我建議你多花點時間用在算法學(xué)習(xí)上吧！

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); 
    
      // 動態(tài)規(guī)劃求最大連續(xù)子序列乘積 
      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) { 
        // 判斷是否為浮點數(shù) 
        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
    ****************************************************************/ 

最新評論