贪心算法 动态规划
2021-05-04 19:29
阅读：690
标签：时间 方法 位置 png mamicode 举例 数值 规划 数组 /* 动态规划 在原地修改数组，将数组每个位置的值更改为当前位置上的最大和。 - 时间复杂度：O(N)O(N)，遍历了一次数组。 贪心算法 动态规划 标签：时间 方法 位置 png mamicode 举例 数值 规划 数组 原文地址：https://www.cnblogs.com/sweet-li/p/13194154.html
* 方法一 贪心法 O(n)
*
* 当叠加的和小于0时，就从下一个数重新开始，
* 同时更新最大和的值(最大值可能为其中某个值)，
* 当叠加和大于0时，将下一个数值加入和中，
* 同时更新最大和的值，依此继续。
*
* 举例： nums = [-2,1,-3,4,-1,2,1,-5,4]
* sum = INT_MIN sum = -2 sum = 1 > 0 ->
* -> sum = -2 sum = 4 > 0 -> sum = 3 > 0 ->
* -> sum = 5 > 0 -> sum = 6 > 0 -> sum = 1 > 0 ->
* -> sum = 5 > 0
* res = [-2, 1, 1, 4, 4, 5, 6, 6, 6]
* 最终返回 res = 6
* */
复杂度分析
- 空间复杂度：O(1)O(1)，使用了常数空间。
评论
亲，登录后才可以留言！