自己的想法。雖然是O(n)氓辣，但是感覺肯定是麻煩了。
習(xí)慣把所有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;
}
}
