Maximum Subarray Sum

A single problem can often be solved using multiple methods with different space and time complexities. Problems such as finding the sums, maxima, minima, or even binary operations involve iterating over the entire data and optionally using another data structure that is well suited to the problem.

One such problem is the maximum subarray sum. Think about a game (like Clash Royale) where you lose or gain points depending on the outcome of each match you play. A very common feature of such games is to show the best streak you have had along with the range of the best streak.

You initially start with 0 points, and since you are new to the game, you would naturally lose the first few games. Let’s assume that your first 3 games looked like:

Your best streak among the first 3 games is 5, and that is in your very second game. The range (following 0-indexing) would be [1,1].

Now that you have figured out the game, you start to win more games than you lose. Let’s assume that the next 5 games look like:

Your streak now becomes 46, i.e., (-3) + (5) + (-1) + (1) + (25) + (19), and that is right from your first game all the way till the sixth game, and your streak range becomes [0,5].

Now let’s extend this to a larger number of matches, and this is what your entire gameplay looks like:

The final streak is 52 and involves your ninth and tenth games.

Code it out!

A few variables initialised…

a = [1, 25, 19, -22, 15, -3, -53, -1, 2, 50, -1]
max_sub, sub_start, sub_stop = float('-inf'), 0, 0

The max_sub variable stores the maximum sum, i.e., the best streak. The [sub_start, sub_stop] are the start and the end of the subarray with the maximum sum, i.e., the start and the end of the streak.

Approach 1

Let’s iterate over all subarrays and calculate the sum of each.

for i in range(len(a)):
    for j in range(i, len(a)):
        sub_sum = 0
        for k in range(i, j + 1):
            sub_sum += a[k] # subarray a[i : j + 1]'s sum

The sub_sum variable stores the sum of the subarray from index i to j (both included). Every time we calculate the subarray sum, we compare it with the already initialised max_sub.

If sub_sum > max_sub, we have a new max_sub, i.e., a better streak, and every time we have a new maximum, we update sub_start and sub_stop with the starts and the ends of the sub_sum, i.e., the start and the stop of the streak.

for i in range(len(a)):
    for j in range(i, len(a)):
        sub_sum = 0
        for k in range(i, j + 1):
            sub_sum += a[k]
        if max_sub < sub_sum: # found a better streak!
            max_sub = sub_sum # update the max_sub with the better streak
            sub_start = i # start of the better streak
            sub_stop = j # end of the better streak

The time complexity of the above method is O(n³), as we iterate through the entire array to generate all sub-arrays (i.e., O(n²)) and then compute the sum of each sub-array (i.e., O (n²)), yielding O(n² x n) = O(n³).

Get Mehul Jain’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The space complexity is the same as the input’s space complexity, i.e., O(n), since we are doing all of this in place. The solution alone is a constant space, i.e., an O(1) solution.

Approach 2

Now, we have a method to get the subarray using just two loops where the end of the subarray (j) always moves ahead by 1, away from the start of the subarray (i).

for i in range(len(a)):
    for j in range(i, len(a)):
        # subarray is basically a[i : j + 1]

The index j is moving by one each time. This means that as j moves, it is already visiting every element of the current subarray. So instead of using another loop to go through the subarray and calculate its sum, we can simply keep adding a[j] to sub_sum.

for i in range(len(a)):
    sub_sum = 0
    for j in range(i, len(a)):
        sub_sum += a[j]

The sub_sum now stores the sum of the subarray. Every time we have a new sub_array, we need to do exactly what we were doing before:

1. Check if sub_sum is greater than max_sum.
2. If yes, we update max_sum with sub_sum and then update the start and end of the subarray with the indices of that subarray with the new maximum sub_sum.

for i in range(len(a)):
    sub_sum = 0
    for j in range(i, len(a)):
        sub_sum += a[j] # Getting the sum of the sub-array a(i,j) by moving j
        if max_sub < sub_sum: # found a better streak!
            max_sub = sub_sum # update the max_sub with the better streak
            sub_start = i # start of the better streak
            sub_stop = j # end of the better streak

The time complexity of the above method is now O(n²) as we iterate through the entire array to get all subarrays and find the sum as and when our subarray size changes by 1.

The space complexity is still the same as O(n) (or O(1) if we exclude the input’s space complexity).

Approach 3

Can we drop the inner loop? Let’s consider two scenarios.

In the first scenario, calculate the sub_sum by iterating through the array; when we come across an element that helps continue the sub_sum, we include it.

sub_sum, max_start = 0, 0
for i in range(len(a)):
    if a[i] < a[i] + sub_sum:
        sub_sum += a[i]

The second scenario is when we say that it is better to start from the current element and drop the previous elements, and hence discard sub_sum (i.e., sub_sum is negative). We update the sub_start to start from the current index.

for i in range(len(a)):
    if a[i] < a[i] + sub_sum:
        sub_sum += a[i]
    else:
        sub_sum = a[i]
        sub_start = i

We still need to keep track of the best subarray we’ve seen so far. So, after calculating the sub_sum, we compare it with max_sub and update it if we've found a better one.

for i in range(len(a)):
    if a[i] < a[i] + sub_sum:
        sub_sum += a[i]
    else:
        sub_sum = a[i]
        sub_start = i # start of the better streak
    if max_sub < sub_sum:
        max_sub = sub_sum # update the max_sub with the better streak
        max_start = sub_start # update start of currently best subarray
        sub_stop = i # end of the better streak

This is a famous algorithm called Kadane’s Algorithm.

The time complexity of the above method is O(n), as we iterate through the entire array once to compute the maximum subarray sum, and the space complexity is the same as in the previous approaches.

Compare it!

The time taken to execute varies with different approaches as expected. Here is another table from CSES’s “Maximum subarray sum” section.

NOTE: Comparing times between the two would not be accurate as the execution environment is different for both. What is more indicative is how the time rises with the size of the array across approaches.

Full Code

a = [1, 25, 19, -22, 501, -3, -53, -1, 2, 50, -1]

# Approach 1
max_sub, sub_start, sub_stop = float('-inf'), 0, 0

for i in range(len(a)):
    for j in range(i, len(a)):
        sub_sum = 0
        for k in range(i, j + 1):
            sub_sum += a[k]
        if max_sub < sub_sum: # found a better streak!
            max_sub = sub_sum # update the max_sub with the better streak
            sub_start = i # start of the better streak
            sub_stop = j # end of the better streak

print(max_sub, sub_start, sub_stop)

# Approach 2
max_sub, sub_start, sub_stop = float('-inf'), 0, 0

for i in range(len(a)):
    sub_sum = 0
    for j in range(i, len(a)):
        sub_sum += a[j]
        if max_sub < sub_sum: # found a better streak!
            max_sub = sub_sum # update the max_sub with the better streak
            sub_start = i # start of the better streak
            sub_stop = j # end of the better streak

print(max_sub, sub_start, sub_stop)

# Approach 3
max_sub, sub_start, sub_stop = float('-inf'), 0, 0

sub_sum, max_start = 0, 0
for i in range(len(a)):
    if a[i] < a[i] + sub_sum:
        sub_sum += a[i]
    else:
        sub_sum = a[i]
        sub_start = i
    if max_sub < sub_sum:
        max_sub = sub_sum # update the max_sub with the better streak
        max_start = sub_start # update the start of the currently best subarray
        sub_stop = i # end of the better streak

print(max_sub, max_start, sub_stop)

Grind?

1. LeetCode — Maximum Subarray
2. CSES — Maximum Subarray Sum