题解 | #连续子数组的最大和#

连续子数组的最大和

http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484

DP / 贪心

状态表示:f[i] 表示以 nums[i] 结尾的连续子数组的最大和 状态计算:

  1. 包含 nums[i],f[i]=f[i1]+nums[i]f[i] = f[i - 1] + nums[i]
  2. 以 nums[i] 开始,f[i]=nums[i]f[i] = nums[i]

f[i] 两者取最大值

最后遍历 f 数组取最大值

全部评论

相关推荐

11-28 17:48
中山大学 C++
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务