/ Data Structure and Algorithms  

Leetcode 53. Maximum Subarray

Question



Find a contiguous subarray in an array that has the largest sum.

Similar Questions

Solution

Dynamic programming can be used here to tackle this problem.

We can use a one-dimensional array dp[i] to represent the largest sum of subarray ending at index i. In other words, the last element of this sub-array is the index i element, and this subarray has the largest sum.

We have 2 situations here:

  • If dp[i-1] < 0, then dp[i] = nums[i]
  • If dp[i-1] >= 0, then dp[i] = dp[i-1] + nums[i]

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// dp array
int[] dp = new int[nums.length];
int result = nums[0];

// base condition
dp[0] = nums[0];

for (int i = 1; i < nums.length; i++) {
    //2 situations to update dp[i]
    if (dp[i - 1] < 0) {
        dp[i] = nums[i];
    } else {
        dp[i] = dp[i - 1] + nums[i];
    }

    // update result
    result = Math.max(result, dp[i]);
}

return result;

Time complexity O(n), and space complexity O(n).

Notice that we only used dp[i-1], so the whole dp array isn’t necessary here. Just need a variable to store the previous value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int previous = nums[0];
int result = nums[0];

for (int i = 1; i < nums.length; i++) {
    //2 situations to update dp[i]
    if (previous < 0) {
        previous = nums[i];
    } else {
        previous = previous + nums[i];
    }

    // update result
    result = Math.max(result, previous);
}

return result;

This way, time complexity is still O(n), but space complexity is optimized O(1).