Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

maximum sum
rectangle
problem
kadane
algorithm

The maximum sub-array sum problem

Educative Answers Team

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:

-34-121-43

In this array of length 77, the sub-array that gives the maximum sum is the continuous array of orange cells, i.e., 66. 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 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);
}

RELATED TAGS

maximum sum
rectangle
problem
kadane
algorithm
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring