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:


# Code

The following code tabs implement the above algorithm: 

#include <iostream>
using namespace std;

int Kadane(int arr[], int n) 
{ 
  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);
}

def Kadane(arr,n): 

   current_maximum = arr[0]   
   maximum_so_far =arr[0]  
      
   for i in range(1,n): 
      current_maximum = max(arr[i], current_maximum + arr[i]) 
      maximum_so_far = max(maximum_so_far,current_maximum) 
          
   return maximum_so_far 
  
arr = [-3, 4, 1, 2, -1, -4, 3] 
print"Maximum sum sum is" , Kadane(arr,len(arr))

Python

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: 