DP solution with O(n) time and O(1) space.

```
class Solution {
public:
// hold: The profit when hold a stock
// sold: The profit when sold the stock
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 0) return 0;
int hold = -prices[0];
int sold = 0;
for(int i = 1; i < n; i++) {
hold = max(hold, -prices[i]);
sold = max(sold, hold + prices[i]);
}
return sold;
}
};
```