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 , the sub-array that gives the maximum sum is the continuous array of orange cells, i.e., . 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_maximumto keep track of whether or not the value at the current index would increase the maximum sum. -
maximum_so_farto 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 ofarr[i]andcurrent_maximum + arr[i]incurrent_maximumitself. -
Store the maximum of
maximum_so_farandcurrent_maximuminmaximum_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);}
RELATED TAGS
