0053. 最大子序和 · ttttt

# 0053. 最大子序和 ## 題目地址(53. 最大子序和) <https://leetcode-cn.com/problems/maximum-subarray/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。示例: 輸入: [-2,1,-3,4,-1,2,1,-5,4] 輸出: 6 解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。進階: 如果你已經實現復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。 ``` ``` ## 前置知識 - [滑動窗口](https://github.com/azl397985856/leetcode/blob/master/thinkings/slide-window.md) - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 百度 - 字節 - 騰訊 - bloomberg - linkedin - microsoft ## 公司 - 阿里、百度、字節、騰訊 ## 思路這道題求解連續最大子序列和，以下從時間復雜度角度分析不同的解題思路。 #### 解法一 - 暴力解（暴力出奇跡，噢耶！）一般情況下，先從暴力解分析，然后再進行一步步的優化。 **原始暴力解：**（超時）求子序列和，那么我們要知道子序列的首尾位置，然后計算首尾之間的序列和。用 2 個 for 循環可以枚舉所有子序列的首尾位置。然后用一個 for 循環求解序列和。這里時間復雜度太高，`O(n^3)`. **復雜度分析** - 時間復雜度：O(N3)O(N ^ 3)O(N3), 其中 N 是數組長度 - 空間復雜度：O(1)O(1)O(1) #### 解法二 - 前綴和 + 暴力解 **優化暴力解：** (震驚，居然 AC 了）在暴力解的基礎上，用前綴和我們可以優化到暴力解`O(n^2)`, 這里以空間換時間。這里可以使用原數組表示`prefixSum`, 省空間。求序列和可以用前綴和（`prefixSum`) 來優化，給定子序列的首尾位置`（l, r),`那么序列和 `subarraySum=prefixSum[r] - prefixSum[l - 1];`用一個全局變量`maxSum`, 比較每次求解的子序列和，`maxSum = max(maxSum, subarraySum)`. **復雜度分析** - 時間復雜度：O(N2)O(N ^ 2)O(N2), 其中 N 是數組長度 - 空間復雜度：O(N)O(N)O(N) > 如果用更改原數組表示前綴和數組，空間復雜度降為`O(1)` 但是時間復雜度還是太高，還能不能更優化。答案是可以，前綴和還可以優化到`O(n)`. #### 解法三 - 優化前綴和 - from [**@lucifer**](https://github.com/azl397985856) 我們定義函數`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(N)O(N), 其中 N 是數組長度 - 空間復雜度：O(1)O(1)O(1) #### 解法四 - [分治法](https://www.wikiwand.com/zh-hans/%E5%88%86%E6%B2%BB%E6%B3%95) 我們把數組`nums`以中間位置（`m`)分為左（`left`)右(`right`)兩部分. 那么有， `left = nums[0]...nums[m - 1]` 和 `right = nums[m + 1]...nums[n-1]` 最大子序列和的位置有以下三種情況： 1. 考慮中間元素`nums[m]`, 跨越左右兩部分，這里從中間元素開始，往左求出后綴最大，往右求出前綴最大, 保持連續性。 2. 不考慮中間元素，最大子序列和出現在左半部分，遞歸求解左邊部分最大子序列和 3. 不考慮中間元素，最大子序列和出現在右半部分，遞歸求解右邊部分最大子序列和分別求出三種情況下最大子序列和，三者中最大值即為最大子序列和。舉例說明，如下圖： ![](https://img.kancloud.cn/fe/bd/febdefc163188ac8595adaa1024b6b85_1440x1080.jpg) **復雜度分析** - 時間復雜度：O(NlogN)O(NlogN)O(NlogN), 其中 N 是數組長度 - 空間復雜度：O(logN)O(logN)O(logN) #### 解法五 - [動態規劃](https://www.wikiwand.com/zh-hans/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92) 動態規劃的難點在于找到狀態轉移方程， `dp[i] - 表示到當前位置 i 的最大子序列和` 狀態轉移方程為： `dp[i] = max(dp[i - 1] + nums[i], nums[i])` 初始化：`dp[0] = nums[0]` 從狀態轉移方程中，我們只關注前一個狀態的值，所以不需要開一個數組記錄位置所有子序列和，只需要兩個變量， `currMaxSum - 累計最大和到當前位置i` `maxSum - 全局最大子序列和`: - `currMaxSum = max(currMaxSum + nums[i], nums[i])` - `maxSum = max(currMaxSum, maxSum)` 如圖： ![](https://img.kancloud.cn/ae/b9/aeb9fd02fead002400112ea8679e9f9a_919x614.jpg) **復雜度分析** - 時間復雜度：O(N)O(N)O(N), 其中 N 是數組長度 - 空間復雜度：O(1)O(1)O(1) ## 關鍵點分析 1. 暴力解，列舉所有組合子序列首尾位置的組合，求解最大的子序列和, 優化可以預先處理，得到前綴和 2. 分治法，每次從中間位置把數組分為左右中三部分，分別求出左右中（這里中是包括中間元素的子序列）最大和。對左右分別深度遞歸，三者中最大值即為當前最大子序列和。 3. 動態規劃，找到狀態轉移方程，求到當前位置最大和。 ## 代碼 (`Java/Python3/Javascript`) #### 解法二 - 前綴和 + 暴力 *Java code* ``` <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; } } ``` ``` *Python3 code*`(TLE)` ``` <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 ``` ``` *Javascript code* from [**@lucifer**](https://github.com/azl397985856) ``` <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 code* ``` <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; } } ``` ``` *Python3 code* ``` <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 ``` ``` *Javascript code* from [**@lucifer**](https://github.com/azl397985856) ``` <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 code* ``` <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)); } } ``` ``` *Python3 code* ``` <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) ``` ``` *Javascript code* from [**@lucifer**](https://github.com/azl397985856) ``` <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 code* ``` <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; } } ``` ``` *Python3 code* ``` <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 ``` ``` *Javascript code* from [**@lucifer**](https://github.com/azl397985856) ``` <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; } ``` ``` ## 擴展 - 如果數組是二維數組，求最大子數組的和？ - 如果要求最大子序列的乘積？ ## 相似題 - [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) - [Longest Turbulent Subarray](https://leetcode.com/problems/longest-turbulent-subarray/) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)