# My C++ solution with O(N) time 8ms

• my solution. With array 'maxDiffFirst' and 'maxDiffSecond' recording the max profit from the beginning and from the end respectively. And the max profit is therefore the max sum of maxDiffFirst[i] and maxDiffSecond[i+1].

`````` class Solution {
public:
int maxProfit(vector<int>& prices) {
int L = prices.size();
if( L<=1 )
return 0;
// fisrt part
vector<int> maxDiffFirst(L,0);
int minBuy = prices[0];
for( int i = 1; i<L; i++ ){
minBuy = minBuy<prices[i-1]? minBuy:prices[i-1];
maxDiffFirst[i] = maxDiffFirst[i-1]>prices[i]-minBuy? maxDiffFirst[i-1]:prices[i]-minBuy;
}
// second part
vector<int> maxDiffSecond(L,0);
int maxSell = prices[L-1];
int ret = maxDiffFirst[L-1];
for( int i = L-2; i>=0; i-- ){
maxSell = maxSell>prices[i+1]? maxSell:prices[i+1];
maxDiffSecond[i] = maxDiffSecond[i+1]>maxSell-prices[i]? maxDiffSecond[i+1]:maxSell-prices[i];
ret = ret>maxDiffSecond[i+1]+maxDiffFirst[i]? ret:maxDiffSecond[i+1]+maxDiffFirst[i];
}
ret = ret>maxDiffSecond[0]? ret:maxDiffSecond[0];
return ret;

}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.