最大子数组和-python-动态规划
·
题目：
思路：
- 典型的动态规划，dp[i]表示以第i位为结尾的最大和
- 状态转移：
- 若dp[i-1]<0,那么dp[i]要想最大，就要舍弃dp[i-1],自己另起门户
- 若dp[i-1]>=0,那么dp[i]要想最大，就要加上dp[i-1]
代码：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):#从第二个数字开始，第一个数字的最大和是自己本身
nums[i] += max(nums[i-1],0)#0比任何负数都大,比任何正数都小
return max(nums)
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
1
0- 0
已为社区贡献30条内容
所有评论(0)