0053. Maximum Subarray.md

题目描述

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.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. 

思路

这道题要求解连续最大的子串的和。

贪心算法：

先设置一个max_sum，它永远存着当前的最大子串的和。

每次只关注当前状态的最大值：设置一个current_sum，当 i 遍历数组 nums 时，比较 nums[i] 和 nums[i]+current_sum 谁更大，更大的值就是新的current_sum。

每次更新完current_sum时，再拿它与max_sum比较，更大的值就是新的max_sum。

当 i 遍历完整个数组时，就得到了答案。

代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_sum = nums[0]
        max_sum = current_sum
        for i in range(1,len(nums)):
            current_sum = max(nums[i], nums[i]+current_sum)
            max_sum = max(max_sum, current_sum)
        return max_sum

• 时间复杂度：O(n)

​