kadane's algorithm gfg
//C++ program to find maximum contiguous subarray using dynamic programming
#include <iostream>
#include <climits>
using namespace std;
void kadane_algo(int arr[],int n){
if(!n) return;
int curr = arr[0],max = arr[0];
for(int i=1;i<n;i++){
//max sum of subarray ending at pos i
curr = curr+arr[i] > arr[i] ? curr+arr[i] : arr[i];
//max sum of subarray ending at any pos so far
max = curr > max ? curr : max;
}
cout<<"Max subarray sum: "<<max<<endl;
}
int main() {
int arr[] = {-1,-4,-6,-7,-4};
int n = sizeof(arr)/sizeof(int);
kadane_algo(arr,n);
return 0;
}