這一章節(jié)會學(xué)習(xí)關(guān)于動態(tài)規(guī)劃相關(guān)問題的算法。先簡單后困難。

53. 最大子序和

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

示例:

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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        '''
        貪心,如果前面數(shù)之和小于0, 則拋棄前面數(shù),以當(dāng)前數(shù)為起點,記錄最大數(shù); 如果大于0, 則加上當(dāng)前數(shù).
        '''
        if not nums:
            return 
        n = len(nums)
        pre = max_num = nums[0]
        for i in range(1, n):
            pre = max(nums[i], pre + nums[i])   # 
            max_num = max(max_num, pre)
        return max_num



    def maxSubArray1(self, nums: List[int]) -> int:
        '''
        dp[i] 表示以i為結(jié)尾的最大子序列之和
        dp思路, 如果前面的數(shù)大于0, 則dp=當(dāng)前數(shù)加上前一個數(shù). 表示當(dāng)前數(shù)之前最大子序列之和
        如果前面的數(shù)小于0, 則當(dāng)前數(shù)為最大子序列之和.
        '''
        if not nums:
            return 
        n = len(nums)
        if n == 1:
            return nums[0]
        for i in range(1, n):
            if nums[i-1] > 0:
                nums[i] = nums[i] + nums[i-1]
        return max(nums)