# Simple O(n) time complexity with O(n) space

#1
``````//Divide the array into two parts for each i and calculate left max and right max for each i. Answer will be max of all lmax+rmax.
int Solution::maxProfit(const vector<int> &A) {
if(A.size() < 2) return 0;
vector<int> sm(A.size());
vector<int> lg(A.size());
sm[0] = A[0];
lg[A.size()-1] = A[A.size()-1];
for(int i = 1; i < A.size(); ++i) {
sm[i] = min(A[i], sm[i-1]);     // calculate smallest from 0 till now
}
for(int j = A.size()-2; j >= 0; --j) {
lg[j] = max(A[j], lg[j+1]);     // calculate largest from A.size()-1 till now
}
int lmax = INT_MIN, rmax = INT_MIN;
rmax = lg[0]-A[0];                  // initialize rmax for right side
int sol = rmax;
for(int i = 0; i < A.size()-1; ++i) {
lmax = max(lmax, A[i]-sm[i]);       // calculate leftside maximum from 0 till i
rmax = lg[i+1]-A[i+1];              // calculate rightside maximum from i+1 to A.size()
sol = max(sol, lmax + rmax);
}
lmax = max(lmax, A[A.size()-1]-sm[A.size()-1]);     // when loop ends, we need to calculate lmax for i = A.size()-1
sol = max(sol, lmax);
return sol;
}``````