0053. 最大子序和
题目地址(53. 最大子序和)
https://leetcode-cn.com/problems/maximum-subarray/
题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。前置知识
公司
阿里
百度
字节
腾讯
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
我们定义函数 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)$
解法四 -分治法
我们把数组nums以中间位置（m)分为左（left)右(right)两部分. 那么有，left = nums[0]...nums[m - 1] 和right = nums[m + 1]...nums[n-1]
最大子序列和的位置有以下三种情况：
考虑中间元素
nums[m], 跨越左右两部分，这里从中间元素开始，往左求出后缀最大，往右求出前缀最大, 保持连续性。不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和
不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和
分别求出三种情况下最大子序列和，三者中最大值即为最大子序列和。
举例说明，如下图：
复杂度分析
时间复杂度：$O(NlogN)$, 其中 N 是数组长度
空间复杂度：$O(logN)$
解法五 -动态规划
动态规划的难点在于找到状态转移方程，
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)
如图：
复杂度分析
时间复杂度：$O(N)$, 其中 N 是数组长度
空间复杂度：$O(1)$
关键点分析
暴力解，列举所有组合子序列首尾位置的组合，求解最大的子序列和, 优化可以预先处理，得到前缀和
分治法，每次从中间位置把数组分为左右中三部分， 分别求出左右中（这里中是包括中间元素的子序列）最大和。对左右分别深度递归，三者中最大值即为当前最大子序列和。
动态规划，找到状态转移方程，求到当前位置最大和。
代码 (Java/Python3/Javascript)
Java/Python3/Javascript)解法二 - 前缀和 + 暴力
Java code
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)
import sysclass 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 maxSumJavascript code from@lucifer
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
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
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 maxSumJavascript code from@lucifer
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
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
import sysclass 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
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
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
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_sumJavascript code from@lucifer
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;}扩展
如果数组是二维数组，求最大子数组的和？
如果要求最大子序列的乘积？
相似题
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最后更新于
这有帮助吗？