53. Maximum Subarray (Medium)

53. Maximum Subarray (Medium) 最大子数组和

题干

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquerapproach, which is more subtle.

解题思路

暴力解法

有一个外层循环，然后对每个循环元素及其后面的数组部分循环切片计算总和。

时间复杂度：O(n^3) - 两层for循环，然后一个求和

可以优化成O(n^2)，通过把前面记录的和记录到备忘录中，下次计算直接使用前一次的值。

这里其实使用的是动态规划中重叠子问题的识别，即[1, 2, 3, …]求和时，所有的可能性如下：

• 1
• 1+2=3
• 3+3=3，这里不用再算1+2，直接复用第二种可能中的1+2=3，可以节省大量计算
• ...

空间复杂度：O(1)

这种方法在leetcode是无法提交的，会超时

技巧解法

重点就是优化时间复杂度，将O(n^2)优化下来。

看一个例子：[-3, -2, -1, 5]，答案应该是5：

暴力解法过程：
sum = -3, -3
sum = -5, -3 + (-2) = -5
sum = -6, -3 + (-2) + (-1) = -6
sum = -1, -3 + (-2) + (-1) + 5 = -1
sum = -2, -2
sum = -3, -2 + (-1) = -3
sum = 2, -2 + (-1) + 5 = 2
sum = -1, -1
sum = 4, -1 + 5 = 4
sum = 5, 5

max_sum = 5

我们会发现里面有很多无效计算，例如：

-3 + (-2) = -5，加上-3，对于-2来说毫无用处；

-5 + (-1) = -6，加上-5，对于-1来说毫无用处；

...

所以可以总结出，备忘录里面计算的值，只要是负数，就可以舍弃，

我的答案

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

这种方法在leetcode是无法提交的，会超时

技巧答案

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # cur_sum初始值为0，是因为后面需要加当前元素
        cur_sum = 0
        # max_sum初始值为第一个元素，是因为初始值设置为任意数都不合适(不能设为0，因为可能存在纯负数的数组)
        max_sum = nums[0]
        for n in nums[1:]:
            if cur_sum < 0:
                cur_sum = 0
            cur_sum += n
            # 和上面三行等同的写法
            # cur_sum = max(n, cur_sum + n)
            max_sum = max(cur_sum, max_sum)
        return max_sum