【简单】Leetcode-53 最大子序和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

解法一

暴力求解。思路简单，时间复杂度为 O(n*n)，会超时

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 暴力
        if not nums: return 0
        res = nums[0]
        for l in range(len(nums)):
            for j in range(l, len(nums)):
                res = max(res, sum(nums[l:j+1]))
        return res

解法二

动态规划。比较迭代过程中比较当前值与 上一次的dp值的和是否有超过当前值，否则只保留当前值填入当前dp即可。时间复杂度O(n), 空间复杂度 O(n)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 动态规划
        dp = [nums[0]] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            # 如果当 num[i] > dp[i-1] + nums[i]，那么可以表示之前的可以舍弃重新开始
            dp[i] = max(nums[i], dp[i-1] + nums[i])
        return max(dp)

解法三

动态规划。时间复杂度O(n), 空间复杂度 O(1)。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 动态规划
        res = cur = nums[0]
        for i in range(1, len(nums)):
            cur = max(nums[i], cur + nums[i])
            res = max(res, cur)
        return res

解法四

回溯 + 分治。分为左中右。看注释理解中间区域

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums: return 0
        return self.__max_sub_array(nums, 0, len(nums) - 1)

    def __max_sub_array(self, nums, left, right):
        if left == right:
            return nums[left]
        mid = left + ((right - left) >> 1)
        # 回溯 + 分治
        return max(self.__max_sub_array(nums, left, mid),
                   self.__max_sub_array(nums, mid + 1, right),
                   self.__max_cross_array(nums, left, mid, right))

    def __max_cross_array(self, nums, left, mid, right):
        # 一定包含 nums[mid] 元素的最大连续子数组的和，
        # 思路是看看左边"扩散到底"，得到一个最大数，右边"扩散到底"得到一个最大数
        # 然后再加上中间数
        left_sum_max, start_left, s1 = 0, mid - 1, 0
        while start_left >= left:
            s1 += nums[start_left]
            left_sum_max = max(left_sum_max, s1)
            start_left -= 1

        right_sum_max, start_right, s2 = 0, mid + 1, 0
        while start_right <= right:
            s2 += nums[start_right]
            right_sum_max = max(right_sum_max, s2)
            start_right += 1
        return left_sum_max + nums[mid] + right_sum_max