Maximum Subarray

Given an array of integers, find a contiguous subarray which has the largest sum.

Example:

Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Solution:

We need to create two sum variables. One is used to track the sum up to now, the other one is used to track the sum from the beginning to some points that lead to the smallest sums (prefix minimum sum). The max difference between the sum and prefix sum will be the maximum subarray.

Code:

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int sum = 0;
        int minSum = 0;
        int max = Integer.MIN_VALUE;
        for (int x : nums) {
            sum += x;
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
        }
        return max;
    }
}