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:

  1. Initialize a current sum (variably called maxEndingHere) equal to the value of the element at the first position in the array (arr[0]).
  2. Iterate through the array. At every position, set maxEndingHere to the maximum of the following two values: maxEndingHere + arr[i] or arr[i], where i is the current position in the array.
  3. Keep track of the greatest maxEndingHere encountered (ex: in a variable called maxSoFar).
  4. Return maxSoFar. This algorithm guarantees a time complexity of O(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 called maxSoFar. 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 and maxSoFar 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, compare maxSoFar with the updated value of maxEndingHere. Since -2 is less than -1 set maxSoFar to -1.
  • This process continues as we advance through the array, modifying maxEndingHere and maxSoFar 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

Code
Output
Loading...

All contributors

Looking to contribute?

Learn More on Codecademy