LeetCode 53. Maximum Subarray - from brute Force to Kadane's algorithm

Link to LeetCode 53. Maximum Subarray problem.

In this post, I'll use LeetCode 53: Maximum Subarray to show how to move from a brute-force approach to Dynamic Programming, and then optimize the space complexity to O(1).

Brute Force approach

The simplest approach is to check all possible subarrays and find the maximum sum.

We use two nested loops: the outer loop determines the starting index of the subarray, while the inner loop gradually extends it to the right.

Time and space complexity for this approach:

Time complexity: O(n²) - we check all possible starting and ending indices.
Space complexity: O(1) - we use only a few variables.

Java solution

class Solution {
  public int maxSubArray(int[] nums) {
    int result = Integer.MIN_VALUE;

    for(int i = 0; i < nums.length; i++) {
      int sum = 0;

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

    return result;
  }
}

What can we optimize?

Notice that for each i, we start the calculation from scratch. However, many subarrays share common elements.

What if, instead of checking every possible subarray, we simply kept track of the best result for a subarray ending at the current index?

This leads us to Dynamic Programming.

Dynamic Programming

Let's define:

dp[i] - the maximum sum of a non-empty subarray that must end at index i.

For each element, there are two options:

Start a new subarray with nums[i].
Extend the best subarray ending at index i - 1.

Recurrence relation:

dp[i] = max(nums[i], dp[i-1] + nums[i])

Base case:

dp[0] = nums[0]

Final answer:

max dp[i], where 0 <= i < n

Algorithm complexity for DP:

Time complexity: O(n) - each element is processed once.
Space complexity: O(n) - we store a dp array of length n.

Java solution

class Solution {
  public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];

    dp[0] = nums[0];
    int result = dp[0];

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

    return result;
  }
}

Notice: We have reduced the time complexity from O(n²) to O(n), but now we use additional memory.

Kadane's algorithm

Java

class Solution {
  public int maxSubArray(int[] nums) {
    int current = nums[0];
    int result = nums[0];

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

    return result;
  }
}

Here

current = Math.max(nums[i], current + nums[i]);

determines whether it is better to start a new subarray or continue the previous one.

result = Math.max(result, current);

stores the maximum sum found so far.

Complexity:

Time complexity: O(n) - a single pass through the array.
Space complexity: O(1) - only two variables are used, regardless of the array size.

Very important questions:

Why does Kadane's algorithm work?

The key idea is that if the maximum subarray sum ending at the previous index is negative, adding it to the current element would only decrease the sum.

For example:

nums = [-4, 2, 3]

At index 0:
current = -4

At index 1:
current = max(2, -4 + 2) = 2

At index 2:
current = max(3, 2 + 3) = 5

On the second step, the algorithm discards -4 and starts a new subarray with 2.

However, it does not completely discard previous results: result keeps track of the largest sum found so far.

This is why the algorithm works correctly even for arrays containing only negative numbers.

See here: 53. Maximum Subarray - a solution using Divide and Conquer approach instead of Kadane's Algorithm. Time and Space complexities are both `O(n log n)`

Step-by-step

Let's take a look at what exactly we've optimized.

Brute Force
Time complexity: O(n²) - we iterate through all possible subarrays. This approach uses little memory but requires a lot of time.

Dynamic Programming
Time complexity: O(n) - we eliminate redundant calculations by storing the optimal sums for each index.

Kadane's Algorithm
Space complexity: O(1) - we remove the DP array and keep only the previous state. The time complexity remains O(n).

LeetCode 53 clearly demonstrates how algorithm optimization happens in two stages. First, we move from Brute Force to Dynamic Programming, reducing the time complexity from O(n²) to O(n) by reusing previously computed results.
Next, we move from a DP Array to Kadane's Algorithm, reducing the space complexity from O(n) to O(1).

The key principle:

If the current DP state depends only on the previous state, we can often eliminate the entire DP array and keep only the necessary variables.