53、Maximum Subarray最大子序和
难度:简单
题目描述
英文:
Given an integer array
nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.中文:
给定一个整数数组
nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例
Example:
1
2
3Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.进阶
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
解题思路
思路一
遍历数组,用curSum
维护当前位置累加的和,当curSum<0
时,将其置为0,重新开始累加,每次都更新全局最大值。
顺序遍历整个数组,当遍历到第i
个值时,有两种情况:
之前遍历过程中的
curSum
始终大于0,假设当前子序列为a,a+1,a+2,...,b-2,b-1,b
,此时考虑所有可能:- 以当前子序列开头为开头,以中间任一处结尾的序列,如
a,a+1,a+2,...b-2
:这种情况一致在遍历过程中保存更新; - 以当前子序列结尾为结尾,以中间任一处开头的序列,如
a+2,...,b-2,b-1,b
:这种情况一定小于当前的完整子序列的和,因为前面缺失的部分的和一定是大于0的(讨论的前提就是遍历过程加和始终大于0); - 以中间元素为开头和结尾的序列,如
a+2,...,b-2
:这种情况,首先按照前一条讨论,补全前面缺失的部分,之后就变成了第一条讨论的情况;
也就是说,
i
前面的所有可能序列情况都已经考虑到了;- 以当前子序列开头为开头,以中间任一处结尾的序列,如
curSum
出现小于0的情况,此时由于已遍历过的连续子序列加和<0
,则遍历过的这个连续子序列不能完整的被包含到新形成的序列中了;而是否要全部放弃,还是保留末尾的部分元素?参考之前的讨论,以当前子序列结尾为结尾,以中间任一处开头的序列的加和是小于完整子序列的,也就是说是<0
的,因为此时遍历过的连续子序列需要全部放弃,即curSum
置0,并重新开始累加。
其中,每次curSum<0
时的下一位置即为和最大的子序列的开始,每次curSum>maxSum
时的位置即为和最大的子序列的结尾。
代码提交
Python3,用时96ms,内存13.6M
时间复杂度:$O (n) $
1 | class Solution: |
思路二
动态规划,用tempSum
保存以第i
个元素结尾的最大连续子序列的和,假设对于元素i
,其前面的所有元素结尾的序列和都已经得到,则以第i
个元素结尾的子序列的和要么是以第i-1
个元素结尾的和最大的子序列加上当前元素,要么就是当前元素本身,即tempSum[i] = max(tempSum[i-1]+nums[i], nums[i])
。(实际等价于看以i-1
个元素结尾的和最大的子序列的和是否小于0,等价于思路一了)当i=0
时,最大子序列和即为tempSum[0] = nums[0]
。
代码提交
Python3,用时104ms,内存14.2M
时间复杂度:$O (n) $
1 | class Solution: |
可以直接用nums
来保存子序列最大和,能节约一点内存,如下:
1 | class Solution: |
思路三
提示说可以尝试用分治法,那么就将整个数组不断切分成子数组,最后选最大值返回。
用二分法切分数组,最大子序和要么在左半部分,要么在右半部分,要么横跨左右两部分(既包含左侧的最后一个元素,也包含右侧的第一个元素),返回这三种情况的最大值即可。
横跨左右两部分的情况,可以从中间位置逐次向左右两侧遍历,并更新最大值。
代码提交
Python3,用时272ms,内存13.7M
时间复杂度:$O(n\log n)$
1 | class Solution: |