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.
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:
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
View all Courses