Solution in O(n) space and time. Better than the editorial (I think)

#1

int Solution::maxProfit(const vector &A)
{
if (A.size() <= 1)
return 0;

if (A.size() <= 3)
{
    int min0 = A[0];
    int max0 = 0;
    for (auto ii : A)
    {
        max0 = max(max0, ii-min0);
        min0 = min(min0, ii);
    }
    return max0;
}


vector<int> maxR(A.size(), 0);
int max0 = A.back();
for (int ii = A.size()-2; ii >= 1; --ii)
{

    maxR[ii] = max(max0 - A[ii], maxR[ii+1]);
    max0 = max(max0, A[ii]);
}

int min0 = A.front();
max0 = 0;

int out = 0;
for (int ii = 1; ii < A.size()-2; ++ii)
{
    max0 = max(max0, A[ii] - min0);
    
    out = max(out, max0 + maxR[ii]);
    
    min0 = min(min0, A[ii]);
}

return out;

}