Maximum Subarray

Question

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.

LeetCodeleetcode.com/problems/maximum-subarray

Solution

/*
@param: int[] input numbers
@return largest sum of subarray
Algorithm: 前缀和解法，记录之前计算的最小前缀和，最大和等于 当前前缀和-之前存在的最小前缀和；
max = curSum - minSum；
*/
public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    int res = Integer.MIN_VALUE, minLeft = 0;
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        res = Math.max(sum - minLeft, res);
        minLeft = Math.min(minLeft, sum);
    }
    return res;
}