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

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

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

解答：

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

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

    解法三、本題除了上述類(lèi)似最大子數(shù)組和的解法，也可以直接用動(dòng)態(tài)規(guī)劃求解（其實(shí)，上述的解法一本質(zhì)上也是動(dòng)態(tài)規(guī)劃，只是解題所表現(xiàn)出來(lái)的具體形式與接下來(lái)的解法二不同罷了。這個(gè)不同就在于下面的解法二會(huì)寫(xiě)出動(dòng)態(tài)規(guī)劃問(wèn)題中經(jīng)典常見(jiàn)的DP方程，而解法一是直接求解）。具體解法如下：
    假設(shè)數(shù)組為a[]，直接利用動(dòng)歸來(lái)求解，考慮到可能存在負(fù)數(shù)的情況，我們用Max來(lái)表示以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]。

下面來(lái)看一道具體的ACM題目
 題目

    題目描述： 
    給定一個(gè)浮點(diǎn)數(shù)序列（可能有正數(shù)、0和負(fù)數(shù)），求出一個(gè)最大的連續(xù)子序列乘積。 
    輸入： 
    輸入可能包含多個(gè)測(cè)試樣例。 
    每個(gè)測(cè)試樣例的第一行僅包含正整數(shù) n（n<=100000），表示浮點(diǎn)數(shù)序列的個(gè)數(shù)。 
    第二行輸入n個(gè)浮點(diǎn)數(shù)用空格分隔。 
    輸入數(shù)據(jù)保證所有數(shù)字乘積在雙精度浮點(diǎn)數(shù)表示的范圍內(nèi)。 
    輸出： 
    對(duì)應(yīng)每個(gè)測(cè)試案例，輸出序列中最大的連續(xù)子序列乘積，若乘積為浮點(diǎn)數(shù)請(qǐng)保留2位小數(shù)，如果最大乘積為負(fù)數(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]來(lái)表示以arr[i]結(jié)尾的最大連續(xù)子序列和，則狀態(tài)轉(zhuǎn)移方程為：

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

and

有了狀態(tài)轉(zhuǎn)移方程，dp代碼就很容易實(shí)現(xiàn)了，看到這里還不理解的同學(xué)，我建議你多花點(diǎn)時(shí)間用在算法學(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); 
    
      // 動(dòng)態(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) { 
        // 判斷是否為浮點(diǎn)數(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
    ****************************************************************/ 

最新評(píng)論