```
class Solution {
public:
int maxProfit(vector<int>& prices) {
const size_t n=prices.size();
if (n<=1)
return 0;
// lowest[i] == lowest price from 0..i
// highest[i] == highest price from i..end
vector<int> lowest;
vector<int> highest(n);
size_t i,j;
int themin=prices[0];
int themax=prices[n-1];
for (i=0;i<n;i++){
themin=min(prices[i],themin);
lowest.push_back(themin);
themax=max(prices[n-i-1],themax);
highest[n-i-1]=(themax);
}
int ans=0;
for (i=0;i<n-1;i++){
ans=max(ans, highest[i+1]-lowest[i]);
}
return ans;
}
};
```