Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
题目
求数组中连续的几个数加起来最大的和。
思路
从第一个开始加，如果第一个数是正数，算一算它加第二个数等于多少，如果第一个数是负数，那就不要第一个数了，从第二个数开始加。如果头两个数的和为正数，那么算一算它加上第三个数是多少，如果头两个数的和是负数，那就从第三个数开始算。以此类推，我们每次都记录一下累加的和，它为正数就继续加，为负数就抛弃，从下一个开始。不过抛弃前先记录一下为正数时的值，最后遍历完了，这个值就是记录的最大值。
代码
public int maxSubArray2(int[] nums) {
int dp=nums[0];//用来计算累加和
int max=dp;
for (int i = 1; i < nums.length; i++) {
if (dp>0) {
dp=dp+nums[i];
}else {
dp=nums[i];
}
max=Math.max(dp, max);
}
return max;
}
