DP有点难。
看到一个不错的讲解，对应的转移方程：
- 在持有 buy[i] = max(sell[i-2] - price[i], buy[i-1])
- 不在持有 sell[i] = max(buy[i-1] + price[i],sell[i-1])
代码的话像覃超说的，转移方程出来了就不要动脑子了。注意Java这边不太好用-1做数组下标。
public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;
int[] buy = new int[prices.length];
int[] sell = new int[prices.length];
buy[0] = -prices[0];
buy[1] = Math.max(-prices[0] , -prices[1]);
sell[0] = 0;
sell[1] = Math.max(prices[1] - prices[0] , 0 );
for (int i = 2; i < prices.length; i++) {
sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);
buy[i] = Math.max(sell[i - 2] - prices[i], buy[i - 1]);
}
return sell[sell.length - 1];
}
}
