LeetCode刷题DAY 19：最大子序和

⭐️⭐️⭐️

1

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。如输入[-2,1,-3]返回1。

2

题解

思路：动态规划

• 第一步，找到中间状态：此处中间状态st[i]表示第i个元素结尾的子数组最大和。
• 第二步，确定状态转移：nums[i]加上一个正数和才会变大，不然还是另起炉灶更有可能得到更大的和。所以当st[i-1]为正数时，st[i]=st[i-1]+nums[i]，否则st[i]=nums[i]。

class Solution:    def maxSubArray(self, nums: List[int]) -> int:        st = nums[0]        for i in range(1,len(nums)):          st.append(max(nums[i],max_list[i-1]+nums[i]))        return max(st)

‍

官方解题视频中给了两个思路，一个是贪心算法：若当前指向元素之前的和小于0，则丢掉当前元素之前的序列；另一个是动态规划：若前一个元素大于0，则将其加到当前元素上。emmm....感觉两种思路很像，不是特别理解本质区别，有兴趣的一起来讨论～