## 最大連續乘積子串 ### 題目描述 給一個浮點數序列，取最大乘積連續子串的值，例如 -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可以使用動態規劃法解決。 #### 解法一 或許，讀者初看此題，可能立馬會想到用最簡單粗暴的方式：兩個for循環直接輪詢。 ```c double maxProductSubstring(double *a, int length) { double maxResult = a[0]; for (int i = 0; i < length; i++) { double x = 1; for (int j = i; j < length; j++) { x *= a[j]; if (x > maxResult) { maxResult = x; } } } return maxResult; } ``` 但這種蠻力的方法的時間復雜度為O(n^2)，能否想辦法降低時間復雜度呢？ #### 解法二 考慮到乘積子序列中有正有負也還可能有0，我們可以把問題簡化成這樣：數組中找一個子序列，使得它的乘積最大；同時找一個子序列，使得它的乘積最小（負數的情況）。因為雖然我們只要一個最大積，但由于負數的存在，我們同時找這兩個乘積做起來反而方便。也就是說，不但記錄最大乘積，也要記錄最小乘積。 假設數組為a[]，直接利用動態規劃來求解，考慮到可能存在負數的情況，我們用maxend來表示以a[i]結尾的最大連續子串的乘積值，用minend表示以a[i]結尾的最小的子串的乘積值，那么狀態轉移方程為： ``` maxend = max(max(maxend * a[i], minend * a[i]), a[i]); minend = min(min(maxend * a[i], minend * a[i]), a[i]); ``` 初始狀態為maxend = minend = a[0]。 參考代碼如下： ```cpp double MaxProductSubstring(double *a, int length) { double maxEnd = a[0]; double minEnd = a[0]; double maxResult = a[0]; for (int i = 1; i < length; ++i) { double end1 = maxEnd * a[i], end2 = minEnd * a[i]; maxEnd = max(max(end1, end2), a[i]); minEnd = min(min(end1, end2), a[i]); maxResult = max(maxResult, maxEnd); } return maxResult; } ``` 動態規劃求解的方法一個for循環搞定，所以時間復雜度為O(n)。 ### 舉一反三 1、給定一個長度為N的整數數組，只允許用乘法，不能用除法，計算任意（N-1）個數的組合中乘積最大的一組，并寫出算法的時間復雜度。 分析：我們可以把所有可能的（N-1）個數的組合找出來，分別計算它們的乘積，并比較大小。由于總共有N個（N-1）個數的組合，總的時間復雜度為O（N2），顯然這不是最好的解法。