題目描述

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大蛤袒，為 6 熄云。

解法一

暴力求解。思路簡(jiǎn)單妙真，時(shí)間復(fù)雜度為 O(n*n)缴允，會(huì)超時(shí)

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

解法二

動(dòng)態(tài)規(guī)劃。比較迭代過(guò)程中比較當(dāng)前值與 上一次的dp值的和是否有超過(guò)當(dāng)前值珍德，否則只保留當(dāng)前值填入當(dāng)前dp即可练般。時(shí)間復(fù)雜度O(n), 空間復(fù)雜度 O(n)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 動(dòng)態(tài)規(guī)劃
        dp = [nums[0]] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            # 如果當(dāng) num[i] > dp[i-1] + nums[i]，那么可以表示之前的可以舍棄重新開(kāi)始
            dp[i] = max(nums[i], dp[i-1] + nums[i])
        return max(dp)

解法三

動(dòng)態(tài)規(guī)劃锈候。時(shí)間復(fù)雜度O(n), 空間復(fù)雜度 O(1)薄料。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 動(dòng)態(tài)規(guī)劃
        res = cur = nums[0]
        for i in range(1, len(nums)):
            cur = max(nums[i], cur + nums[i])
            res = max(res, cur)
        return res

解法四

回溯 + 分治。分為左中右泵琳∩阒埃看注釋理解中間區(qū)域

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] 元素的最大連續(xù)子數(shù)組的和，
        # 思路是看看左邊"擴(kuò)散到底"获列，得到一個(gè)最大數(shù)谷市，右邊"擴(kuò)散到底"得到一個(gè)最大數(shù)
        # 然后再加上中間數(shù)
        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