Maximum Subarray Sum

Problem: Given an array of integers, find the subarray whose elements add up to the largest sum, and return the sum.

For example, given [-1, 2, 3, -5, 4, 6, -2, 3], return 11 because the subarray with the largest sum is [4, 6, -2, 3].

Constraints:

  • The length of the array is between 1 and 10e4.
  • An element is between -10e4 and 10e4.
Table of contents

Initial thought process (Brute-force)

How do we find the subarray with the largest sum? The most straight-forward way to solve the problem is to try all subarrays. A subarray can be defined by the starting and the ending position. We just need to try all such positions.

In addition, we observe that we don’t need to find the actual subarray with the largest sum. We simply need to find the value of such a sum. This thought process leads to the following brute-force implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public maxSubarraySum(int[] arr) {
        int n = arr.length;
        int maxSum = Integer.MIN_VALUE;

        // Fix the starting position for the subarray
        for (int i = 0; i < n; i++) {
            int curSum = 0;

            // Try all ending position while keeping track of the current sum.
            for (int j = i; j < n; j++) {
                curSum = curSum + arr[j];

                // Keep track of the maximum sum found so far.
                maxSum = Math.max(maxSum, curSum);
            }
        }

        return maxSum;
    }
}

We have a nested loop. The outer loop fixes the starting position of a subarray. Having fixed the starting position, the inner loop grows the subarray one element at a time by trying out all possible ending positions. The inner loop also keeps track of the current sum of the subarray, and the maximum sum of all subarrays seen so far.

Complexity

Let N be the length of the input. We iterate through the array N + (N-1) + (N-2) + ... + 1 times. Therefore, the time complexity is O(N^2).

Another way to think about this time complexity is the number of ways to pick two items from the array, as starting and ending positions. Duplicate must be allowed because the starting and the ending position can be the same. This is known as “multiset coefficient” whose value is given as (n+k-1)!/k!(n-1)! where n is the number of elements and k is the number of duplicates allowed. Therefore, we get N * (N+1) / 2 which is equivalent to N + (N-1) + (N-2) + ... + 1.

The space complexity is constant because we do not need to allocate any memory proportionally to the input size.

Optimization (Kadane’s Algorithm)

One thing we notice about our brute-force algorithm is that it performs duplicate work. It keeps iterating through the same elements. How can we do better? We can work backwards from our observation that we don’t need to find the actual subarray, but rather we just need to find the maximum sum.

Observations from an Example

Let’s iterate through an example input while keeping track of the current sum of the subarray under consideration, and the maximum sum we found so far.

[-1, 2, 3, -5, 4, 6, -2, 3]
  ^
subarray = [-1]
maxSum = -1
curSum = -1

[-1, 2, 3, -5, 4, 6, -2, 3]
     ^
subarray = [-1, 2]
maxSum = 1
curSum = 1

[-1, 2, 3, -5, 4, 6, -2, 3]
        ^
subarray = [-1, 2, 3]
maxSum = 4
curSum = 4

In the first three iteration, we keep growing the subarray one element at a time, and the sum keeps growing.

[-1, 2, 3, -5, 4, 6, -2, 3]
            ^
subarray = [-1, 2, 3, -5]
maxSum = 4
curSum = -1

When we encounter -5, the current sum becomes -1. Here, we don’t want to start a new subarray [-5], but rather keep growing the existing subarray to [-1, 2, 3, -5]. The reason is that we are interested in finding the maximum sum of a subarray (contiguous elements). The sum of the subarray [-5] is worse than that of the subarray [-1, 2, 3, -5].

[-1, 2, 3, -5, 4, 6, -2, 3]
               ^
subarray = [4]
maxSum = 4
curSum = 4

On the other hand, when we encounter 4, we want to start a new subarray. If we grow the existing subarray to [-1, 2, 3, -5, 4], the sum will be 3. But if we start a new subarray, [4], then the sum will be 4. This observation leads to the rule in the following section.

[-1, 2, 3, -5, 4, 6, -2, 3]
                  ^
subarray = [4, 6]
maxSum = 10
curSum = 10

[-1, 2, 3, -5, 4, 6, -2, 3]
                      ^
subarray = [4, 6, -2]
maxSum = 10
curSum = 8

[-1, 2, 3, -5, 4, 6, -2, 3]
                         ^
subarray = [4, 6, -2, 3]
maxSum = 11
curSum = 11

In the rest of the iterations, we grow the existing array one by one, and arrive at the maximum sum of 11.

Rules

We can generalize the observation from the example as a set of rules. Let’s iterate through the array. At a position i,

  1. If arr[i] > curSum + arr[i], then curSum = arr[i].
  2. Otherwise, curSum = curSum + arr[i].

The first rule corresponds to the case of starting a new subarray. And the second rule is equivalent to growing an existing subarray.

Implementation

The rules above lead to the following algorithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int maxSubArray(int[] arr) {
        int maxSum = Integer.MIN_VALUE;
        int curSum = 0;

        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];

            if (curSum + num < num) {
                // Start a new subarray
                curSum = num;
            } else {
                // Grow the existing subarray
                curSum = curSum + num;
            }

            maxSum = Math.max(maxSum, curSum);
        }

        return maxSum;
    }
}

Let’s make sure that we validate the input according to the constraints of the problem.

 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

class Solution {
    public int maxSubArray(int[] arr) {
        // Validate the input
        validateInput(arr);

        // ...
    }

    private void validateInput(int[] arr) {
        int n = arr.length;
        if (n < 1 || n > 10e5) {
            throw new IllegalArgumentException(
                "The input array has an invalid length."
            );
        }

        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];

            if (num < -Math.pow(10, 4) || num > 10e4) {
                throw new IllegalArgumentException(
                    String.format(
                        "The input array has a number that is out of bound '%d'.",
                        num
                    )
                );
            }
        }
    }
}

Complexity

Let N be the size of the input array. The time complexity is O(N) because the algorithm iterates through the input array a constant number of times. The space complexity is O(1) because the algorithm does not allocate any space proportionally to the size of the input.

By the way, this algorithm is known as Kadane’s algorithm. But the interview questions are not aimed at testing presupposed knowledge of algorithms. They are more about giving you the opportunity to demonstrate your thought process at problem solving. By observing and generalizing a set of rules, we were able to optimize the brute-force approach into an optimal solution.

Follow up

Return the subarray with the maximum sum

What if we want to return the subarray with the maximum sum, rather than merely the sum? We can extend the algorithm to keep track of the starting and ending positions of the maximum sum subarray.

 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
34
35
36

class Solution {
    public int maxSubArray(int[] arr) {
        validateInput(arr);

        int curSum = 0;

        // Keep track of the starting and ending positions of
        // the maximum sum subarray.
        int start = -1;
        int end = -1;

        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];

            if (curSum + num < num) {
                // Start a new subarray
                curSum = num;

                start = i;
                end = i;
            } else {
                curSum = curSum + num;

                // Grow the existing subarray
                end = i;
            }
        }

        // Create the subarray and return.
        int[] ans = new int[end - start + 1];
        for (int i = start; i < end; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }
}

What if empty subarrays are allowed?

If empty subarrays are to be considered, then we the minimum sum of a subarray will be 0 because sum of all elements of an empty array is 0. Two changes are required: firstly, we will need to initialize maxSum as 0. Also, we will need to avoid setting curSum to a negative number when we start a new subarray.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int maxSubArray(int[] arr) {
        validateInput(arr);

        int maxSum = 0;
        int curSum = 0;

        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];

            if (curSum + num < num) {
                // Start a new subarray
                curSum = Math.max(0, num);
            } else {
                // Grow the existing subarray
                curSum = curSum + num;
            }

            maxSum = Math.max(maxSum, curSum);
        }

        return maxSum;
    }
}

Lessons Learned

  1. Run a logic through an example input to observe behaviors and generalize them into a set of rules.
  2. When a nested loop is touching the same elements repeatedly, explore what can be done to avoid duplicate computation.