kadaneAlgo.cpp

#include <iostream>
using namespace std;

int main() {
	//code
	int testCases;
	cin>>testCases;
	for(int i = 0; i < testCases; i++) {
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int j=0;j<n;j++){
	        cin>>arr[j];
	    }
	    int max_now = arr[0], max_total = arr[0];
	    int right =1;
	    while(right < n) {
	        if(arr[right] + max_now > arr[right]) {
	            max_now = arr[right] + max_now;
	        } else {
	            max_now = arr[right];
	        }
	        if(max_total  < max_now) {
	            max_total = max_now;
	        }
	        right++;
	    }
	    cout<<max_total<<"\n";
	}
	return 0;
}