自己的想法。虽然是O(n)，但是感觉肯定是麻烦了。
习惯把所有stock问题都用同一种模板了。
public class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length <= 1) return 0;
int n = prices.length;
int dp[] = new int[n];
dp[0] = 0;
dp[1] = prices[1]-prices[0]>0? prices[1]-prices[0]:0;
int max_tmp = prices[0] > prices[1] ? -prices[1]:-prices[0];
for (int i=2; i<n; i++) {
dp[i] = Math.max(max_tmp+prices[i], dp[i-1]);
max_tmp = Math.max(max_tmp, dp[i-2]-prices[i]);
}
return dp[n-1];
}
}
更好的，更简单的解法。空间O(1)
public class Solution {
public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
for(int price : prices) {
prev_buy = buy;
buy = Math.max(prev_sell - price, prev_buy);
prev_sell = sell;
sell = Math.max (prev_buy + price, prev_sell);
}
return sell;
}
}
