[LeetCode] Problem 53 - Maximum Subarray

Posted on | In ,

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.

Follow up

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

O(nlogn) runtime, O(logn) stack space – Divide and Conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int maxSubArray(int[] nums) {
    return subArrayHelper(nums, 0, nums.length - 1);
}

private int subArrayHelper(int[] nums, int left, int right){
    if (left > right)
        return Integer.MIN_VALUE;

    int middle = (left + right) >> 1;

    int leftSum = subArrayHelper(nums, left, middle - 1);
    int rightSum = subArrayHelper(nums, middle + 1, right);

    int sum = 0;
    int sumFromLeft = 0;

    for (int i = middle - 1; i >= left; i--){
        sum += nums[i];
        sumFromLeft = Math.max(sumFromLeft, sum);
    }

    sum = 0;
    int sumFromRight = 0;

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

    int middleSum = sumFromLeft + sumFromRight + nums[middle];

    return Math.max(middleSum, Math.max(leftSum, rightSum));
}

O(n) runtime, O(1) space – Dynamic programming

1
2
3
4
5
6
7
8
9
10
11
public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length+1];
    int max = Integer.MIN_VALUE;

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

    return max;
}