53. Maximum Subarray

Medium (LinkedIn, Bloomberg, Microsoft)

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Solution 1: time complexity is O(n), space complexity is O(n)

public class Solution {

// test case:
// nums is empty

public int maxSubArray(int[] nums) {
    if(nums == null || nums.length == 0) {
        return 0;
    }

    int[] sums = new int[nums.length];
    sums[0] = nums[0];
    int maxSum = nums[0];

    for(int i = 1; i < nums.length; i++) {
        sums[i] = Math.max(sums[i - 1] + nums[i], nums[i]);
        maxSum = Math.max(maxSum, sums[i]);
    }

    return maxSum;
}

}

Follow up: improve the space complexity to O(1)

public class Solution {

// test case:
// nums is empty

public int maxSubArray(int[] nums) {
    if(nums == null || nums.length == 0) {
        return 0;
    }

    int sum = nums[0];
    int maxSum = nums[0];

    for(int i = 1; i < nums.length; i++) {
        sum = Math.max(sum + nums[i], nums[i]);
        maxSum = Math.max(maxSum, sum);
    }

    return maxSum;
}

}