力扣-贪心/动归dp-持续更新中。。。。。。

一.53 最大子数组和

1.题目

53. 最大子数组和 - 力扣（LeetCode）

 2.视频题解

【看起来复杂，其实是简单动态规划 | LeetCode：53.最大子序和-哔哩哔哩】 https://b23.tv/V8C4um9

DP的思路

五部曲：dp含义，递推公式，初始化，遍历顺序，打印

dp含义：令dp[i]=以第i个下表为结尾的最大子序和

递推公式：dp[i]=max(dp[i-1]+nums[i],nums[i])

要么要链接上前面一坨，要不从num[i]开始从新开始

初始化：dp[0]=nums[0]

遍历顺序：根据递推公式能够看出是从前往后遍历

for i in range(1, len(nums)):

        一边遍历，得到dp[i],一边记录最大的子序，这样可以节省一次遍历，找dp[i]的最大值

3.代码 

class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""f = [0] * len(nums)f[0] = nums[0]result=f[0]for i in range(1, len(nums)):f[i] = max(f[i - 1]+nums[i],nums[i])if result<f[i]:result=f[i]return result

还有一种方法使用了前缀和+贪心的方法：53. 最大子数组和 - 力扣（LeetCode）

详细灵神的题解 ：

class Solution:def maxSubArray(self, nums: List[int]) -> int:ans = -infmin_pre_sum = pre_sum = 0for x in nums:pre_sum += x  # 当前的前缀和ans = max(ans, pre_sum - min_pre_sum)  # 减去前缀和的最小值min_pre_sum = min(min_pre_sum, pre_sum)  # 维护前缀和的最小值return ans

二.