leetcode动态规划问题

这一章节会学习关于动态规划相关问题的算法。先简单后困难。

53. 最大子序和

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

示例:

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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        '''
        贪心,如果前面数之和小于0, 则抛弃前面数,以当前数为起点,记录最大数; 如果大于0, 则加上当前数.
        '''
        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为结尾的最大子序列之和
        dp思路, 如果前面的数大于0, 则dp=当前数加上前一个数. 表示当前数之前最大子序列之和
        如果前面的数小于0, 则当前数为最大子序列之和.
        '''
        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)