#include <iostream>
using namespace std;
#include<bits/stdc++.h>
 
int main() {
	// your code goes here
	int arr[] = {-2,1,-3,4,-1,2,1,-5,4};
	int n = sizeof(arr)/sizeof(int);
	//there are i+1 subarrays ending at i we have to find the maximum subarray sum ending at i 
	vector<int>p1; int maxsum = INT_MIN; int curr_sum = arr[0];
	for(int i = 1 ; i <n ; i++){
	    curr_sum = max({curr_sum+arr[i],arr[i],0}); //curr_sum = p1[i] =max( p[i-i]+ arr[i],arr[i],0)
	   maxsum =max(curr_sum,maxsum);
 
	}
	cout<<maxsum;
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgoKaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglpbnQgYXJyW10gPSB7LTIsMSwtMyw0LC0xLDIsMSwtNSw0fTsKCWludCBuID0gc2l6ZW9mKGFycikvc2l6ZW9mKGludCk7CgkvL3RoZXJlIGFyZSBpKzEgc3ViYXJyYXlzIGVuZGluZyBhdCBpIHdlIGhhdmUgdG8gZmluZCB0aGUgbWF4aW11bSBzdWJhcnJheSBzdW0gZW5kaW5nIGF0IGkgCgl2ZWN0b3I8aW50PnAxOyBpbnQgbWF4c3VtID0gSU5UX01JTjsgaW50IGN1cnJfc3VtID0gYXJyWzBdOwoJZm9yKGludCBpID0gMSA7IGkgPG4gOyBpKyspewoJICAgIGN1cnJfc3VtID0gbWF4KHtjdXJyX3N1bSthcnJbaV0sYXJyW2ldLDB9KTsgLy9jdXJyX3N1bSA9IHAxW2ldID1tYXgoIHBbaS1pXSsgYXJyW2ldLGFycltpXSwwKQoJICAgbWF4c3VtID1tYXgoY3Vycl9zdW0sbWF4c3VtKTsKCSAgIAoJfQoJY291dDw8bWF4c3VtOwoJCglyZXR1cm4gMDsKfQ==