1.動態(tài)規(guī)劃

思路：令狀態(tài) $dp[i]$ 表示以 $A[i]$ 作為末尾的連續(xù)序列的最大和（即 $A[i]$ 必須作為連續(xù)序列的末尾）

通過這個 $dp[\ ]$ 數(shù)組蜂怎，要求的最大子序和其實就是 $dp[0]限佩，dp[1]实辑，…，dp[n-1]$ 中的最大值。

現(xiàn)作如下考慮：因為 $dp[i]$ 要求是必須以 $A[i]$ 結尾的連續(xù)序列，那么只有兩種情況：

這個最大和的連續(xù)序列只有一個元素，即以 $A[i]$ 開始挽唉，以 $A[i]$ 結尾。
這個最大和的連續(xù)序列有多個元素筷狼，即從前面某處 $A[p]$ 開始 $(p<i)$ 瓶籽，一直到 $A[i]$ 結尾。

對第1種情況桑逝，最大和就是 $A[i]$ 本身棘劣。

對第2種情況，最大和是 $dp[i-1] + A[i]$ 楞遏，即 $A[p]+...+A[i-1] + A[i] = dp[i-1] + A[i]$ 茬暇。

于是得到狀態(tài)轉移方程： $dp[i] = max\left\{A[i], \ dp[i-1]+A[i]\right\}$ 首昔，其中 $dp[0] = A[0]$

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n

        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
        
        return max(dp)

空間優(yōu)化：

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

2.分治

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        return self.calc(nums, 0, n - 1)
    
    def calc(self, nums:List[int], l:int, r:int) -> int:
        if l == r:
            return nums[l]
        
        mid = (l + r) // 2
        
        left = self.calc(nums, l, mid)
        right = self.calc(nums, mid + 1, r)
        
        lmax, lsum = nums[mid], 0
        for i in range(mid, l - 1, -1):
            lsum += nums[i]
            lmax = max(lmax, lsum)
        
        rmax, rsum = nums[mid + 1], 0
        for i in range(mid + 1, r + 1):
            rsum += nums[i]
            rmax = max(rmax, rsum)
        
        return max(left, right, lmax + rmax)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        return Solution.calc(self, nums, 0, n - 1)
    
    def calc(self, nums:List[int], l:int, r:int) -> int:
        if l == r:
            return nums[l]
        
        mid = (l + r) // 2
        
        left = Solution.calc(self, nums, l, mid)
        right = Solution.calc(self, nums, mid + 1, r)
        
        lmax, lsum = nums[mid], 0
        for i in range(mid, l - 1, -1):
            lsum += nums[i]
            lmax = max(lmax, lsum)
        
        rmax, rsum = nums[mid + 1], 0
        for i in range(mid + 1, r + 1):
            rsum += nums[i]
            rmax = max(rmax, rsum)
        
        return max(left, right, lmax + rmax)

Python類中方法相互調用的兩種方式：

類名.方法名(self)
注意：方法名內(nèi)必須傳入一個實例對象的指針，self后可根據(jù)方法定義放入適當實參
self.方法名(方法列表)
方法列表不應該包括self

最后編輯于：2020.09.16 15:12:02

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者