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來記錄當(dāng)前和的值。
如果cur的值是負(fù)數(shù)不可能作為子數(shù)組的左邊數(shù)組。所以如果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;
}
