O(n) Kadane's Algo with Negative Elements Checked


#1

int Solution::maxSubArray(const vector &A) {
int n = A.size();
int ans = 0, sum = 0;
bool cond = true;
for (int i=0;i<n;i++) {
if (sum + A.at(i) > 0) {
sum+=A.at(i);
cond = false;
} else {
sum = 0;
}
ans = max(ans,sum);
}
if (!cond) {
return ans;
} else {
return *max_element(A.begin(),A.end());
}
}