*Dynamic programming*

we use OPT[k] refers to the maximum profit we can get from first k stocks.

For a given stock, there are three possible implementations: buy, sell, neither of those two.

In order to simplify this problem, we can merge buy and neither together.

1. sell: OPT[k] = max(OPT[i-2]+`v(k)`

-`v(i)`

) (2<=i<k)

2. not sell: OPT[k] = OPT[k-1]

```
public int maxProfit(int[] prices) {
if (prices.length==0) return 0;
int[] profit = new int[prices.length];
for(int i = 1; i < prices.length; i++){
profit[i] = profit[i-1];
for(int j = i-1; j>= 0; j--){
if(prices[i] > prices[j]){
int temp = 0;
if(j-2 > 0) temp = profit[j-2];
temp += prices[i]-prices[j];
if(temp > profit[i]) profit[i] = temp;
}
}
}
return profit[prices.length-1];
}
```