*Without dynamic programming*


#1
int Solution::maxProfit(const vector<int> &A) {
    // without Dynamic programming.
    if(A.empty())   return 0;
    int n = A.size(), res = 0;
    int left[n], right[n];
    
    int min_val = A[0], max_val = A[n - 1];
    left[0] = 0, right[n - 1] = 0;
    for(int i = 1; i < n; i++){
        min_val = min(min_val, A[i]);
        left[i] = max(left[i - 1], A[i] - min_val);
        max_val = max(max_val, A[n - 1 - i]);
        right[n - 1 - i] = max(right[n - i], max_val - A[n - 1 - i]);
    }
    for(int i = 0; i < n; i++)
        res = max(res, left[i] + right[i]);
    return res;
}