【剑指offer】连续子数组的最大和

连续子数组的最大和

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

典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和,如果dp[n-1]>0,dp[n]=dp[n]+dp[n-1],因为当前数字加上一个正数一定会变大;如果dp[n-1]<0,dp[n]不变,因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可。

public int FindGreatestSumOfSubArray(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
        max = Math.max(max, array[i]);
    }
    return max;
}
全部评论
思路挺好的,但也只能在刷题的时候这么写吧,如果是在生产代码上这么写,方法的调用方会很惊讶,因为这个方***改变数组中的内容,当调用方将数组传递到别的逻辑时,可能会产生想不到的结果。如果要避免,调用方则要拷贝一份array再传递给这个方法,那这样其实不如让方法实现者自己开辟一块dp数组。面试的时候这么跟面试官提一下,其实很能提现水平和自己的思考。
6 回复 分享
发布于 2021-02-03 12:56
太强了,array存储的就是dp
3 回复 分享
发布于 2020-05-08 23:02
想问问你们怎么炼成这种思维的,太厉害了
2 回复 分享
发布于 2020-08-17 09:19
array[i] += Math.max(array[i - 1], 0); //换成这样好理解一点
1 回复 分享
发布于 2020-07-21 12:10
宇宙最强答案
1 回复 分享
发布于 2020-04-09 20:42
思路清晰的一
点赞 回复 分享
发布于 2023-08-22 20:41 湖南
牛皮,不明觉厉!
点赞 回复 分享
发布于 2023-05-24 21:47 广东
可能大佬的思维比较跳跃吧,建议解释中的两个算式改为 如果dp[n-1]>0,dp[n]=array[n]+dp[n-1];如果dp[n-1]<0,则dp[n]=array[n],意思是从当前元素起重新开始一段序列;
点赞 回复 分享
发布于 2022-11-19 14:56 陕西
数组全为负数呢?
点赞 回复 分享
发布于 2021-09-29 09:26
您把 array 为 null 时的错误检验给忘记了,建议改一下
点赞 回复 分享
发布于 2021-07-28 18:10
全是负数呢
点赞 回复 分享
发布于 2021-04-12 14:37
真滴牛!
点赞 回复 分享
发布于 2021-03-01 17:15
TMD看不懂啊
点赞 回复 分享
发布于 2021-02-19 21:10
漂亮!
点赞 回复 分享
发布于 2021-01-30 14:18
楼主强的一匹
点赞 回复 分享
发布于 2021-01-05 20:49
能教教我吗,看了一个多小时没看懂
点赞 回复 分享
发布于 2020-11-28 00:09
牛!
点赞 回复 分享
发布于 2020-11-09 11:57
清楚
点赞 回复 分享
发布于 2020-10-17 18:47
牛逼 言简意赅
点赞 回复 分享
发布于 2020-10-11 19:04
public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if (array == null || array.length == 0) { return 0; } int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i-1] >= 0) { array[i] += array[i-1]; } if (max < array[i]) { max = array[i]; } } return max; } }
点赞 回复 分享
发布于 2020-09-28 20:21

相关推荐

不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
评论
174
31
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务