# 0053. 最大子序和 ### 题目地址(53. 最大子序和) ### 题目描述 ``` 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 ``` ### 前置知识 * [滑动窗口](/leetcode-solution/thinkings/slide-window.md) * [动态规划](/leetcode-solution/thinkings/dynamic-programming.md) ### 公司 * 阿里 * 百度 * 字节 * 腾讯 * bloomberg * linkedin * microsoft ### 思路 这道题求解连续最大子序列和，以下从时间复杂度角度分析不同的解题思路。 **解法一 - 暴力解 （暴力出奇迹， 噢耶！）** 一般情况下，先从暴力解分析，然后再进行一步步的优化。 **原始暴力解：**（超时） 求子序列和，那么我们要知道子序列的首尾位置，然后计算首尾之间的序列和。用 2 个 for 循环可以枚举所有子序列的首尾位置。 然后用一个 for 循环求解序列和。这里时间复杂度太高，`O(n^3)`. **复杂度分析** * 时间复杂度：$O(N ^ 3)$, 其中 N 是数组长度 * 空间复杂度：$O(1)$ **解法二 - 前缀和 + 暴力解** **优化暴力解：** (震惊，居然 AC 了） 在暴力解的基础上，用前缀和我们可以优化到暴力解`O(n^2)`, 这里以空间换时间。 这里可以使用原数组表示`prefixSum`, 省空间。 求序列和可以用前缀和（`prefixSum`) 来优化，给定子序列的首尾位置`（l, r),` 那么序列和 `subarraySum=prefixSum[r] - prefixSum[l - 1];` 用一个全局变量`maxSum`, 比较每次求解的子序列和，`maxSum = max(maxSum, subarraySum)`. **复杂度分析** * 时间复杂度：$O(N ^ 2)$, 其中 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,2,...,i-1`，中的最小值即可。 因此我们需要 用一个变量来维护这个最小值，还需要一个变量维护最大值。 **复杂度分析** * 时间复杂度：$O(N)$, 其中 N 是数组长度 * 空间复杂度：$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://p.ipic.vip/kg4yvp.jpg) **复杂度分析** * 时间复杂度：$O(NlogN)$, 其中 N 是数组长度 * 空间复杂度：$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://p.ipic.vip/f5g6y3.jpg) **复杂度分析** * 时间复杂度：$O(N)$, 其中 N 是数组长度 * 空间复杂度：$O(1)$ ### 关键点分析 1. 暴力解，列举所有组合子序列首尾位置的组合，求解最大的子序列和, 优化可以预先处理，得到前缀和 2. 分治法，每次从中间位置把数组分为左右中三部分， 分别求出左右中（这里中是包括中间元素的子序列）最大和。对左右分别深度递归，三者中最大值即为当前最大子序列和。 3. 动态规划，找到状态转移方程，求到当前位置最大和。 ### 代码 (`Java/Python3/Javascript`) **解法二 - 前缀和 + 暴力** *Java code* ```java 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)` ```python 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) ```javascript 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* ```java 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* ```python 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) ```javascript 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* ```java 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* ```python 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) ```javascript 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* ```java 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* ```python 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) ```javascript 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 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/w6dpse.jpg) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/53.maximum-sum-subarray-cn.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.