Maximum Subarray Sum Solution using Kadane’s Algorithm

Maximum Subarray Sum is an interesting problem that provides insight into different ways to solving a problem.

The important point is that each solution to the problem has a different time complexity. And as a result, this problem acts as a good example of how we should think about solving our problems in more efficient ways.

In this post, we will look at the problem and its possible solutions using C++ arrays.

The Maximum Subarray Sum Problem Statement

The problem statement is as follows:

Given an array of n numbers, the task is to calculate the maximum subarray sum. In other words, the goal is to find the largest possible sum of sequence of consecutive values in the array.

As an example, consider the below array:

It has a mix of positive and negative values. However, the subarray having maximum sum in this array is highlighted below:

This subarray has a sum of 10. In other words, the maximum sum when compared to other subarrays that can be formed out of this array. And hence, the answer to the problem is 10.

Our goal is to write an algorithm or a program to find this maximum subarray sum. If you are not sure what an array is, do check out this detailed introduction to arrays.

Solution # 1 – Brute Force

The most straightforward approach to solve this problem is to find out all the possible subarrays and calculate the sum of values in all those subarrays. By maintaining the largest sum in a separate variable, we will have the answer at the end when we process all subarrays.

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> array = {-1, 2, 4, -3, 5, 2, -5, 2};

    int highest = 0;

    for (int a = 0; a < array.size(); a++)
    {
        for (int b = a; b < array.size(); b++)
        {
            int sum = 0;
            for (int k = a; k <= b; k++)
            {
                sum = sum + array[k];
            }
            highest = std::max(highest, sum);
        }
    }

    std::cout << "The Highest Sum is: " << highest << std::endl;
}

Here, a & b store the first and last index of the current subarray. Also, the variable highest stores the maximum subarray sum at any given point of time. At the end of the whole processing, the variable will have the highest sum in the array.

As we can see, this solution works. However, it is not very efficient. Basically, there are 3 nested loops in this solution. And therefore, the overall time complexity of this solution comes out as O(n³).

Solution # 2 – The Intermediate Solution

The first solution can be optimized by removing one loop from it. Below is how we can do that:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> array = {-1, 2, 4, -3, 5, 2, -5, 2};

    int highest = 0;

    for (int a = 0; a < array.size(); a++)
    {
        int sum = 0;
        for (int b = a; b < array.size(); b++)
        {
            sum = sum + array[b];
            highest = std::max(highest, sum);
        }
    }

    std::cout << "The Highest Sum is: " << highest << std::endl;
}

In this, we calculate the sum of the subarray whenever b moves. Due to this, we are able to cut down on one loop.

The time complexity of this solution is O(n²). However, we can do better in this solution and bring it down to linear time complexity.

Solution # 3 – The Kadane’s Algorithm

This solution is also known as Kadane’s Algorithm since the solution is attributed to J.B. Kadane.

In this approach, only one loop is enough to solve the problem. The idea behind this approach is to break the overall problem into sub-problems. In other words, we find out the maximum subarray sum at each position in the array.

Consider the below table showing maximum subarray at each position for our sample array.

As we can see, at each step of the loop we calculate the maximum sum of the subarray till that position. So for example, at index 0, the maximum subarray sum is -1 because only one index is considered.

At index 1, we check the current element and the sum calculated till index 0 to calculate the new sum. If that sum is more than the maximum till that point, we update the maximum.

After the loop is over, the value stored in the maximum is indeed the value of the maximum subarray sum.

Below is the implementation of the algorithm in C++.

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> array = {-1, 2, 4, -3, 5, 2, -5, 2};

    int highest = 0;
    int sum = 0;

    for (int i = 0; i < array.size(); i++)
    {
        sum = std::max(array[i], sum + array[i]);
        highest = std::max(sum, highest);
    }

    std::cout << "The Highest Sum is: " << highest << std::endl;
}

Pretty slim implementation, isn’t it?

The time complexity of this algorithm is O(n). Since it is only going to iterate once through the entire array.

With this, we have successfully implemented the Maximum Subarray Sum solution using Kadane’s Algorithm.

If you have any comments or queries, please do mention in the comments section below.