In this lesson, given a 1-D array, we’ll find a contiguous subarray with the maximum sum.

Sample program

The Original Array:       { -100 4 2 7 13 0 -4 6 -10 5 }

The Maximum Sum Subarray: { 4 2 7 13 0 -4 6 } 
With the sum of :         28

For this problem, we’ll write the simpler and more straightforward version of the code first. Then, we’ll optimize the code using some elegant observations and techniques resulting in a more efficient algorithm.

This is going to be a very interesting lesson.

Finding the maximum sum subarray

Think of the subarray as a window of varying sizes (dynamic-sized array) that we extend across the array to find the contiguous values with the maximum sum.

If all the values were positive, we could say the entire array, when added, gives the maximum sum.

However, we can have negative values too.

For example, we can have a 1-D array called A of size 6, initialized as below:

A[6]={5, -20, 15, 16, -3, -5}

Here, if we were to find the subarray with the maximum sum, we would need to check all the possible windows.

Exploring all the possible windows

For exploring all the possible windows, we can think in the following fashion: anchor one position (s) and change the next position one by one.

The subarray with the maximum sum would be as follows:

{15, 16} with the sum of 31.

Exhaustive search: Displaying all the possible windows

To display all the possible windows, we’ll need two for loops, where the first for loop checks all the points as starting points one by one and the second for loop checks all the points as ending points.

So, the number of pairs would be n2n^2 atleast.

In the code editor below, s is our starting index and e is our ending index, and note that e is initialized with s. Click “Run” to see the output.

#include <iostream>
#include <unistd.h>
using namespace std;
void allPossibleWindows(int A[], int Size)
{
	// for each starting point 
	for (int s = 0; s < Size; s++)
	{
		// for each ending point
		cout << "Anchored at[" << s << "]" << endl;
		for (int e = s; e < Size; e++)
		{
			cout << "[" << s << "," << e << "]: ";
			cout << "{";
			for (int i = s; i <= e; i++)
				cout << A[i] << " ";
			cout << "}" << endl;
		}
		cout << endl;
	}
}
int main()
{
	int A[6] = { 5, -20, 15, 16, -3, -5}, Size = 6;
	allPossibleWindows(A, Size);
	return 0;
}
Finding all the possible windows

Subarray with maximum sum (slower version)

Now that we’ve seen that to test all the possible windows, we’ll need at least two for loops. We’ll use the most straightforward approach to find the subarray with the maximum sum.

So, the idea is as follows:

for each window
   1. Compute the sum
   2. Check if it is maximum
         Update max

Using three nested loops

Let’s create a function called MaximumSumSubArraySlow3Nested() that takes the array, size, and starting and ending indexes as parameters.

int MaximumSumSubArraySlow3Nested(int A[ ], int Size, int &msi, int &mei);

The idea is quite simple. Like finding the maximum value from an array, we declare the Max variable and assign it with the value A[0]. Next,we save msi=0, mei=0 considering that the first value is the maximum value, where the msi,mei pair represents the range of the maximum subarray.

Can we initialize Max with 0?

No, we can’t. There may be negative values in the array (we can even have an array having all the negative values), so we shouldn’t initialize it with 0. Instead, we set Max equal to the first value of the array, assuming that it’s the maximum, and update it during comparison.

During each window, we aggregate all the values inside a window anchored at [s,e] in Sum and compare Sum with Max. In case Max is smaller, we update Max along with the window’s coordinates in msi=s and mei=e.

Let’s look at the code below:

#include <iostream>
#include <iomanip>
#include <unistd.h>
using namespace std;

int MaximumSumSubArraySlow3Nested(int A[], int Size, int &msi, int &mei)
{
	int Max = A[0];
	msi = 0;
	mei = 0;

	for (int s = 0; s < Size; s++)
	{
		int Sum;
		for (int e = s; e < Size; e++)
		{
			Sum = 0;

			for (int i = s; i <= e; i++)
				Sum += A[i];

			if (Max < Sum)
			{
				msi = s, mei = e, Max = Sum;
			}
		}
	}

	return Max;
}

void PrintSubArray(const char Msg[], int A[], int si, int ei)
{
	cout << Msg << ": { ";
	for (int i = si; i <= ei; i++)
	{
		cout << A[i] << " ";
	}

	cout << "}";
}

int main()
{
	int A[10] = {-100, 4, 2, 7, 13, 0, -4, 6, -10, 5}, Size = 10;
	int msi, mei;
	int MaxSum = MaximumSumSubArraySlow3Nested(A, Size, msi, mei);
	PrintSubArray("The Original Array", A, 0, Size - 1);
	PrintSubArray("\n\nThe Maximum Sum Subarray", A, msi, mei);
	cout << " with sum of : " << MaxSum << endl;

	return 0;
}
Finding the subarray with the maximum sum (three nested loops)

  • In line 17, we must initialize Sum=0 before starting the third nested loop (because the previously accumulated summation should be discarded).

Subarray with maximum sum (slow version)

Let’s tweak our code a bit to try and make it more efficient than our last code version.

Pause for a moment here and think of what we can do to optimize the code above. Look at the following illustration:

Notice that once the start of the window is anchored, the two consecutive windows differ by only one element, i.e., the next extended window is nothing but the previously summed window and the added last element. So, computing the summation again is not needed. Therefore, the third nested loop can easily be avoided.

See the code below:

#include <iostream>
#include <iomanip>
#include <unistd.h>
using namespace std;

int MaximumSumSubArraySlow2Nested(int A[], int Size, int &msi, int &mei)
{
	int Max = A[0];
	msi = 0;
	mei = 0;

	for (int s = 0; s < Size; s++)
	{
		int Sum = 0;
		for (int e = s; e < Size; e++)
		{
			// Sum = 0;
			// for(int i=s+1; i<=e; i++)
			Sum += A[e];

			if (Max < Sum)
			{
				msi = s, mei = e, Max = Sum;
			}
		}
	}

	return Max;
}

void PrintSubArray(const char Msg[], int A[], int si, int ei)
{
	cout << Msg << ": { ";
	for (int i = si; i <= ei; i++)
	{
		cout << A[i] << " ";
	}

	cout << "}";
}

int main()
{
	int A[10] = {-100, 4, 2, 7, 13, 0, -4, 6, -10, 5}, Size = 10;
	int msi, mei;
	int MaxSum = MaximumSumSubArraySlow2Nested(A, Size, msi, mei);
	PrintSubArray("The Original Array", A, 0, Size - 1);
	PrintSubArray("\n\nThe Maximum Sum Subarray", A, msi, mei);
	cout << " with sum of : " << MaxSum << endl;

	return 0;
}
Finding the subarray with the maximum sum (two nested loops)

Subarray with maximum sum (fast version: Kadane’s algorithm)

Let’s try and see if we can make it even more efficient. What do you think we can do to optimize it?

A clever observation

From an anchored position, instead of exhaustively extending all the windows (and calculating the sum), we should immediately stop extending the windows and leave the anchor at the start position if the window sum is negative.

Obviously, if the sum of a window is negative, then for any value which extends this window, the aggregation will further decrease the summation.

Implementation using one loop

Using the above observations, if the sum at some point becomes negative, we do not need to continue computing the sum any further. We can immediately start a new window with an updated starting point.

Let’s suppose we have an array A:

A[] = {3, 9, -15, 40, 5};

The sum of the first two elements is 3 + 9 = 12. Now, 12 + (-15) = -3. The Sum now holds a negative number, -3. If we were to continue computing the Sum, it would be 37 (-3 + 40 = 37), which is less than 40. We’ll start a new window from 40—the last window containing the values 40 and 5 will be the maximum subarray.

This is why there is no need for us to iterate through all the windows exhaustively.

Here’s the summary:

We keep extending the window until the sum becomes negative. When it does, we leave all the intermediate anchor positions and move the anchor one step ahead of the position where the sum becomes negative. During the loop, we keep comparing with the maximum and maintain its position and value.

This approach is known as Kadane’s algorithm. It makes our solution very efficient.

Look at the animation below and understand it’s working:

Let’s look at the code below:

#include <iostream>
#include <iomanip>
#include <unistd.h>
using namespace std;

int MaximumSumSubArrayFASTKadane_Algo(int A[], int Size, int &msi, int &mei)
{
	int Max = A[0];
	msi = 0;
	mei = 0;
	int Sum;
	for (int s = 0, e = 0; e < Size; e++)
	{
		Sum += A[e];
		if (Max < Sum)
		{
			msi = s, mei = e, Max = Sum;
		}

		if (Sum < 0)	// As soon as the window Sum is -ve we must need to leave that window
		{
			Sum = 0;    // resetting the Sum to zero
						// Start of the new window
						// we ignore all the intermediate anchors
						// from s till e
			s = e + 1;  // setting the new anchor
		}				
	}					

	return Max;
}

void PrintSubArray(const char Msg[], int A[], int si, int ei)
{
	cout << Msg << ": { ";
	for (int i = si; i <= ei; i++)
	{
		cout << A[i] << " ";
	}

	cout << "}";
}

int main()
{
	int A[10] = {-100, 4, 2, 7, 13, 0, -4, 6, -10, 5}, Size = 10;
	int msi, mei;
	int MaxSum = MaximumSumSubArrayFASTKadane_Algo(A, Size, msi, mei);
	PrintSubArray("The Original Array", A, 0, Size - 1);
	PrintSubArray("\n\nThe Maximum Sum Subarray", A, msi, mei);
	cout << " with sum of : " << MaxSum << endl;

	return 0;
}
Finding the subarray with the maximum sum (one nested loop)