41最大子数组

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;
    }