2. Intuitive C++ Solution


#1

Use a prefix array. https://en.wikipedia.org/wiki/Prefix_sum
and then use array that stores min of the prefixes.

//code

int Solution::maxSubArray(const vector &A) {
int n=A.size();
int prefix[n]={0}, minA[n]={0};
prefix[0]=A[0];
minA[0]=prefix[0];
for(int i=1;i<n;i++){
prefix[i]=prefix[i-1]+A[i];
minA[i]=min(minA[i-1],prefix[i]);
}

 for(int i=0;i<n;i++){
    prefix[i]=prefix[i]-minA[i];
}

int t= *max_element(prefix,prefix+n);
if(t==0) return *max_element(A.begin(),A.end());
return t;

}