# Problem Solving: Finding the Maximum Sum Window in a 1-D array

Use the sliding window technique to find the contiguous subarray with the maximum sum in a 1-D array.

## We'll cover the following

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 $n^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 pointfor (int s = 0; s < Size; s++){// for each ending pointcout << "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;}

### 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; }

- 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; }

### 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; }