Related Tags

maximum sum
rectangle
problem
algorithm

# The maximum sub-array sum problem

The maximum sub-array sum problem asks you to find a continuous sub-array with the largest sum.

Take a look at the array below:

In this array of length $7$, the sub-array that gives the maximum sum is the continuous array of orange cells, i.e., $6$. Any other possible sub-array gives a sum lower than or equal to 6.

The most optimal solution for obtaining the maximum sub-array is Kadane’s algorithm; it uses two variables:

• current_maximum to keep track of whether or not the value at the current index would increase the maximum sum.

• maximum_so_far to keep track of the overall maximum that is propagated along the array.

## Algorithm

• Set both of the above-mentioned variables to the value at the first index, i.e., arr[0].

• For the next index i, store the maximum of arr[i] and current_maximum + arr[i] in current_maximum itself.

• Store the maximum of maximum_so_far and current_maximum in maximum_so_far.

• Repeat the above two steps for the remaining indices.

• Return the value of maximum_so_far.

See the illustration below:

1 of 7

## Code

The following code tabs implement the above algorithm:

#include <iostream>
using namespace std;

{
int current_maximum = arr[0];
int maximum_so_far = arr[0];

for (int i = 1; i < n; i++)
{
current_maximum = max(arr[i], current_maximum+arr[i]);
maximum_so_far = max(maximum_so_far, current_maximum);
}
return maximum_so_far;
}

int main()
{
int arr[] =  {-3, 4, -1, 2, 1, -4, 3};
int n = 7;
cout << "maximum sum is " << Kadane(arr, n);
}

RELATED TAGS

maximum sum
rectangle
problem