Given an array of integers, find a contiguous subarray which has the largest sum.
Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
我们可以定义一个max来记录最大值。定义cur来记录当前和的值。
如果cur的值是负数不可能作为子数组的左边数组。所以如果cur为0就要清空。
public int maxSubArray(int[] nums) {
// write your code here
int max=Integer.MIN_VALUE;
int cur=0;
for (int i = 0; i < nums.length; i++) {
cur+=nums[i];
max=Math.max(max, cur);
if (cur<=0) {
cur=0;
}
}
return max;
}
