Kadane's Algorithm
Published Dec 15, 2023
Contribute to Docs
Kadane's algorithm
is a dynamic programming approach to efficiently finding the maximum sum of a subarray in a given array of numbers. The algorithm works as follows:
- Initialize a current sum (variably called
maxEndingHere
) equal to the value of the element at the first position in the array (arr[0]
). - Iterate through the array. At every position, set
maxEndingHere
to the maximum of the following two values:maxEndingHere + arr[i]
orarr[i]
, wherei
is the current position in the array. - Keep track of the greatest
maxEndingHere
encountered (ex: in a variable calledmaxSoFar
). - Return
maxSoFar
. This algorithm guarantees a time complexity ofO(n)
, making it an optimal solution for this problem.
Example
Here’s how Kadane’s algorithm can be applied to a problem:
- Consider the array {-2, -1, -3, 4, -1, 2, 1, -5, 4}. Initialize two integer variables: one named
maxEndingHere
and the other calledmaxSoFar
. These variables serve to track the maximum subarray sum ending at the current position and the overall maximum subarray sum. - The loop commences with the first element, which is -2. Therefore, both
maxEndingHere
andmaxSoFar
are initially -2. - Proceed to the next element, -1, and compare it to the sum of itself and the previous value of
maxEndingHere
. Since -1 is greater than the sum of -2 and -1, setmaxEndingHere
to -1. Also, comparemaxSoFar
with the updated value ofmaxEndingHere
. Since -2 is less than -1 setmaxSoFar
to -1. - This process continues as we advance through the array, modifying
maxEndingHere
andmaxSoFar
at each step. - After the loop, the variable
maxSoFar
contains the maximum subarray sum. - Return the value of
maxSoFar
, which represents the maximum subarray sum.
The following implementation of Kadane's algorithm
is done in c++:
#include <iostream>using namespace std;int maxSubarraySum(int arr[], int size) {int maxEndingHere = arr[0];int maxSoFar = arr[0];for (int i = 1; i < size; i++) {maxEndingHere = max(arr[i], maxEndingHere + arr[i]);maxSoFar = max(maxSoFar, maxEndingHere);}return maxSoFar;}int main() {int nums[] = {-2, -1, -3, 4, -1, 2, 1, -5, 4};int size = sizeof(nums) / sizeof(nums[0]);int maxSum = maxSubarraySum(nums, size);cout << "Maximum subarray sum: " << maxSum << endl;return 0;}
The output for the above code is:
Maximum subarray sum: 6
Codebyte Example
Contribute to Docs
- Learn more about how to get involved.
- Edit this page on GitHub to fix an error or make an improvement.
- Submit feedback to let us know how we can improve Docs.