Kadane's algorithm is used to find the maximum sum subarray in a given array of integers. The algorithm is efficient and has a time complexity of O(n). Here's the C++ code for Kadane's algorithm with an example:
C++ code example:
#include <iostream>
#include <climits>
int kadanesAlgorithm(int arr[], int size) {
int maxEndingHere = 0;
int maxSoFar = INT_MIN;
for (int i = 0; i < size; ++i) {
maxEndingHere = std::max(arr[i], maxEndingHere + arr[i]);
maxSoFar = std::max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
int main() {
const int size = 8;
int arr[size] = {-2, -3, 4, -1, -2, 1, 5, -3};
int maxSum = kadanesAlgorithm(arr, size);
std::cout << "Maximum contiguous sum is: " << maxSum << std::endl;
return 0;
}
In this example, the input array is {-2, -3, 4, -1, -2, 1, 5, -3}, and the maximum sum subarray is {4, -1, -2, 1, 5}, which has a sum of 7. The algorithm efficiently calculates this result in a single pass through the array.
Explanation:
- `maxEndingHere` keeps track of the maximum sum ending at the current index.
- `maxSoFar` keeps track of the maximum sum encountered so far.
- For each element in the array, `maxEndingHere` is updated to be the maximum of the current element and the sum of the current element and `maxEndingHere`.
- `maxSoFar` is updated to be the maximum of `maxSoFar` and `maxEndingHere`.
The final result is the maximum sum subarray, and in this example, it is printed as 7.
