一文看懂《最大子序列和問題》 · ttttt

# 一文看懂《最大子序列和問題》 # 一文看懂《最大子序列和問題》最大子序列和是一道經典的算法題， leetcode 也有原題《53.maximum-sum-subarray》，今天我們就來徹底攻克它。 ## 題目描述求取數組中最大連續子序列和，例如給定數組為 A = \[1， 3， -2， 4， -5\]，則最大連續子序列和為 6，即 1 + 3 +（-2）+ 4 = 6。去首先我們來明確一下題意。 - 題目說的子數組是連續的 - 題目只需要求和，不需要返回子數組的具體位置。 - 數組中的元素是整數，但是可能是正數，負數和 0。 - 子序列的最小長度為 1。比如： - 對于數組 \[1, -2, 3, 5, -3, 2\], 應該返回 3 + 5 = 8 - 對于數組 \[0, -2, 3, 5, -1, 2\], 應該返回 3 + 5 + -1 + 2 = 9 - 對于數組 \[-9, -2, -3, -5, -3\], 應該返回 -2 ## 解法一 - 暴力法（超時法）一般情況下，先從暴力解分析，然后再進行一步步的優化。 ### 思路我們來試下最直接的方法，就是計算所有的子序列的和，然后取出最大值。記 Sum\[i,....,j\]為數組 A 中第 i 個元素到第 j 個元素的和，其中 0 <= i <= j < n，遍歷所有可能的 Sum\[i,....,j\] 即可。我們去枚舉以 0,1,2...n-1 開頭的所有子序列即可，對于每一個開頭的子序列，我們都去枚舉從當前開始到 n-1 的所有情況。這種做法的時間復雜度為 O(N^2), 空間復雜度為 O(1)。 ### 代碼 JavaScript: ``` <pre class="calibre18">``` function LSS(list) { const len = list.length; let max = -Number.MAX_VALUE; let sum = 0; for (let i = 0; i < len; i++) { sum = 0; for (let j = i; j < len; j++) { sum += list[j]; if (sum > max) { max = sum; } } } return max; } ``` ``` Java： ``` <pre class="calibre18">``` class MaximumSubarrayPrefixSum { public int maxSubArray(int[] nums) { int len = nums.length; int maxSum = Integer.MIN_VALUE; int sum = 0; for (int i = 0; i < len; i++) { sum = 0; for (int j = i; j < len; j++) { sum += nums[j]; maxSum = Math.max(maxSum, sum); } } return maxSum; } } ``` ``` Python 3: ``` <pre class="calibre18">``` import sys class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) maxSum = -sys.maxsize sum = 0 for i in range(n): sum = 0 for j in range(i, n): sum += nums[j] maxSum = max(maxSum, sum) return maxSum ``` ``` 空間復雜度非常理想，但是時間復雜度有點高。怎么優化呢？我們來看下下一個解法。 ## 解法二 - 分治法 ### 思路我們來分析一下這個問題，我們先把數組平均分成左右兩部分。此時有三種情況： - 最大子序列全部在數組左部分 - 最大子序列全部在數組右部分 - 最大子序列橫跨左右數組對于前兩種情況，我們相當于將原問題轉化為了規模更小的同樣問題。對于第三種情況，由于已知循環的起點（即中點），我們只需要進行一次循環，分別找出左邊和右邊的最大子序列即可。所以一個思路就是我們每次都對數組分成左右兩部分，然后分別計算上面三種情況的最大子序列和，取出最大的即可。舉例說明，如下圖： ![](https://img.kancloud.cn/97/05/970539c0aba68a4596261ba3dbd35d48_1440x1080.jpg)(by [snowan](https://github.com/snowan)) 這種做法的時間復雜度為 O(N\*logN), 空間復雜度為 O(1)。 ### 代碼 JavaScript: ``` <pre class="calibre18">``` function helper(list, m, n) { if (m === n) return list[m]; let sum = 0; let lmax = -Number.MAX_VALUE; let rmax = -Number.MAX_VALUE; const mid = ((n - m) >> 1) + m; const l = helper(list, m, mid); const r = helper(list, mid + 1, n); for (let i = mid; i >= m; i--) { sum += list[i]; if (sum > lmax) lmax = sum; } sum = 0; for (let i = mid + 1; i <= n; i++) { sum += list[i]; if (sum > rmax) rmax = sum; } return Math.max(l, r, lmax + rmax); } function LSS(list) { return helper(list, 0, list.length - 1); } ``` ``` Java: ``` <pre class="calibre18">``` class MaximumSubarrayDivideConquer { public int maxSubArrayDividConquer(int[] nums) { if (nums == null || nums.length == 0) return 0; return helper(nums, 0, nums.length - 1); } private int helper(int[] nums, int l, int r) { if (l > r) return Integer.MIN_VALUE; int mid = (l + r) >>> 1; int left = helper(nums, l, mid - 1); int right = helper(nums, mid + 1, r); int leftMaxSum = 0; int sum = 0; // left surfix maxSum start from index mid - 1 to l for (int i = mid - 1; i >= l; i--) { sum += nums[i]; leftMaxSum = Math.max(leftMaxSum, sum); } int rightMaxSum = 0; sum = 0; // right prefix maxSum start from index mid + 1 to r for (int i = mid + 1; i <= r; i++) { sum += nums[i]; rightMaxSum = Math.max(sum, rightMaxSum); } // max(left, right, crossSum) return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right)); } } ``` ``` Python 3 : ``` <pre class="calibre18">``` import sys class Solution: def maxSubArray(self, nums: List[int]) -> int: return self.helper(nums, 0, len(nums) - 1) def helper(self, nums, l, r): if l > r: return -sys.maxsize mid = (l + r) // 2 left = self.helper(nums, l, mid - 1) right = self.helper(nums, mid + 1, r) left_suffix_max_sum = right_prefix_max_sum = 0 sum = 0 for i in reversed(range(l, mid)): sum += nums[i] left_suffix_max_sum = max(left_suffix_max_sum, sum) sum = 0 for i in range(mid + 1, r + 1): sum += nums[i] right_prefix_max_sum = max(right_prefix_max_sum, sum) cross_max_sum = left_suffix_max_sum + right_prefix_max_sum + nums[mid] return max(cross_max_sum, left, right) ``` ``` ## 解法三 - 動態規劃 ### 思路我們來思考一下這個問題，看能不能將其拆解為規模更小的同樣問題，并且能找出遞推關系。我們不妨假設問題 Q(list, i) 表示 list 中以索引 i 結尾的情況下最大子序列和，那么原問題就轉化為 Q(list, i), 其中 i = 0,1,2...n-1 中的最大值。我們繼續來看下遞歸關系，即 Q(list, i)和 Q(list, i - 1)的關系，即如何根據 Q(list, i - 1) 推導出 Q(list, i)。如果已知 Q(list, i - 1)，我們可以將問題分為兩種情況，即以索引為 i 的元素終止，或者只有一個索引為 i 的元素。 - 如果以索引為 i 的元素終止，那么就是 Q(list, i - 1) + list\[i\] - 如果只有一個索引為 i 的元素，那么就是 list\[i\] 分析到這里，遞推關系就很明朗了，即`Q(list, i) = Math.max(0, Q(list, i - 1)) + list[i]` 舉例說明，如下圖： ![](https://img.kancloud.cn/2b/d2/2bd2628b1833f28de92d544ae5b96598_919x614.jpg)(by [snowan](https://github.com/snowan)) 這種算法的時間復雜度 O(N), 空間復雜度為 O(1) ### 代碼 JavaScript: ``` <pre class="calibre18">``` function LSS(list) { const len = list.length; let max = list[0]; for (let i = 1; i < len; i++) { list[i] = Math.max(0, list[i - 1]) + list[i]; if (list[i] > max) max = list[i]; } return max; } ``` ``` Java: ``` <pre class="calibre18">``` class MaximumSubarrayDP { public int maxSubArray(int[] nums) { int currMaxSum = nums[0]; int maxSum = nums[0]; for (int i = 1; i < nums.length; i++) { currMaxSum = Math.max(currMaxSum + nums[i], nums[i]); maxSum = Math.max(maxSum, currMaxSum); } return maxSum; } } ``` ``` Python 3: ``` <pre class="calibre18">``` class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) max_sum_ending_curr_index = max_sum = nums[0] for i in range(1, n): max_sum_ending_curr_index = max(max_sum_ending_curr_index + nums[i], nums[i]) max_sum = max(max_sum_ending_curr_index, max_sum) return max_sum ``` ``` ## 解法四 - 數學分析 ### 思路我們來通過數學分析來看一下這個題目。我們定義函數 S(i) ，它的功能是計算以 0（包括 0）開始加到 i（包括 i）的值。那么 S(j) - S(i - 1) 就等于從 i 開始（包括 i）加到 j（包括 j）的值。我們進一步分析，實際上我們只需要遍歷一次計算出所有的 S(i), 其中 i 等于 0,1,2....,n-1。然后我們再減去之前的 S(k),其中 k 等于 0，1，i - 1，中的最小值即可。因此我們需要用一個變量來維護這個最小值，還需要一個變量維護最大值。這種算法的時間復雜度 O(N), 空間復雜度為 O(1)。其實很多題目，都有這樣的思想，比如之前的《每日一題 - 電梯問題》。 ### 代碼 JavaScript: ``` <pre class="calibre18">``` function LSS(list) { const len = list.length; let max = list[0]; let min = 0; let sum = 0; for (let i = 0; i < len; i++) { sum += list[i]; if (sum - min > max) max = sum - min; if (sum < min) { min = sum; } } return max; } ``` ``` Java: ``` <pre class="calibre18">``` class MaxSumSubarray { public int maxSubArray3(int[] nums) { int maxSum = nums[0]; int sum = 0; int minSum = 0; for (int num : nums) { // prefix Sum sum += num; // update maxSum maxSum = Math.max(maxSum, sum - minSum); // update minSum minSum = Math.min(minSum, sum); } return maxSum; } } ``` ``` Python 3: ``` <pre class="calibre18">``` class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) maxSum = nums[0] minSum = sum = 0 for i in range(n): sum += nums[i] maxSum = max(maxSum, sum - minSum) minSum = min(minSum, sum) return maxSum ``` ``` ## 總結我們使用四種方法解決了`《最大子序列和問題》`, 并詳細分析了各個解法的思路以及復雜度，相信下次你碰到相同或者類似的問題的時候也能夠發散思維，做到`一題多解，多題一解`。實際上，我們只是求出了最大的和，如果題目進一步要求出最大子序列和的子序列呢？如果要題目允許不連續呢？我們又該如何思考和變通？如何將數組改成二維，求解最大矩陣和怎么計算？這些問題留給讀者自己來思考。