kadane algorithm with negative numbers included as sum
#include <iostream>
#include <climits>
int kadaneAlgorithm(int arr[], int size) {
int maxEndingHere = arr[0];
int maxSoFar = arr[0];
for (int i = 1; i < size; ++i) {
maxEndingHere = std::max(arr[i], maxEndingHere + arr[i]);
maxSoFar = std::max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Maximum sum subarray: " << kadaneAlgorithm(arr, size) << std::endl;
return 0;
}