Leetcode刷题之旅--剑指 Offer 42. 连续子数组的最大和
程序员文章站
2024-03-23 17:42:52
...
题目描述:
思路: 动态规划!每个dp用来代表累加和,如果前一个的和小于0则不加上这个和重新开始,这是因为如果累加和小于0意味着这个累加和对当前数字就没有贡献,加上这个和还不如这个数本身大。只需要每次比较累加和的当前最大的累加和做对比即可。
class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
for(int i=1;i<nums.length;i++){
nums[i]+=Math.max(nums[i-1],0);
max=Math.max(max,nums[i]);
}
return max;
}
}
上一篇: 简单题--700. 二叉搜索树中的搜索
下一篇: mysql之同表复制插入数据