#include <bits/stdc++.h>
using namespace std;

// O(N) time and O(1) Space
int maxSubArray(vector<int>& nums) {
// INT_MIN is negative infinity
	int maxSoFar = INT_MIN;
	int maxEndingHere = 0;
	    
	for (int i = 0; i < nums.size(); i++) {
	        maxEndingHere += nums[i];	    
	        maxSoFar = max(maxSoFar, maxEndingHere);	    
	        maxEndingHere = max(maxEndingHere, 0);
	    }
	    
	    return maxSoFar;
}

// Naive approach O(N^2) time and O(1) Space
int naive(vector<int>& nums){
	int sum=INT_MIN;
	for(int i = 0; i<nums.size();i++){
		int temp = 0;
		for(int j =i+1;j<nums.size();j++){
			temp += nums[j];
			if(sum < temp){
				sum =temp;
			}
		}
	}
	return sum;
}

int main(){
	vector<int> arr ={-2,1,-3,4,-1,2,1,-5,4};
	cout<<maxSubArray(arr);
	return 0;
}