```
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 0) return 0;
vector<int> min_p(n), max_p(n);
min_p[0] = prices[0];
for(int i = 1; i < n; i ++) min_p[i] = min(min_p[i-1], prices[i]);
max_p[n-1] = prices[n-1];
for(int i = n - 2; i >= 0; i --) max_p[i] = max(max_p[i+1], prices[i]);
int ret = 0;
int tmp = 0;
for(int i = 0; i < n; i ++){
tmp = max(tmp, prices[i] - min_p[i]);
ret = max(ret, tmp + max_p[i] - prices[i]);
}
return ret;
}
```

};