The Maximum Subarray

• Time : O(n)
• Space : O(1)

c++

vector<int> maxSubarray(vector<int> A) {
    int subseq = 0, subarr = -1e8;
    int kadane = 0;
    for(auto& a : A) {
        kadane = max(kadane + a, a);
        subarr = max(subarr, kadane);
        if(a > 0) subseq += a;
    }
    
    if(subseq == 0) subseq = *max_element(begin(A), end(A));
    return {subarr, subseq};
}