121. Best Time to Buy and Sell Stock
121
這個比較簡單秋泄，大致思想：
1.如果sale-buy<=0艺挪，則該價格適合買入被丧。
2.否則判斷該價格賣出的價格是否最好儿礼。
代碼如下：
public int maxProfit(int[] prices) {
if(prices==null||prices.length==0){
return 0;
}
int res = 0;
int buy = prices[0];
for(int i=1;i<prices.length;i++){
if(prices[i]-buy<=0){
buy=prices[i];
}else{
res = Math.max(res,prices[i]-buy);
}
}
return res;
}
122. Best Time to Buy and Sell Stock II
122
這道和上一道題的唯一區(qū)別就是允許多次買賣乍钻「匮總的策略就是買漲~~一直買買賣。
以下代碼是我寫的银择。
public int maxProfit(int[] prices) {
if(prices==null||prices.length==0){
return 0;
}
int res = 0;
int buy = prices[0];
for(int i=1;i<prices.length;i++){
if(prices[i]-buy<=0){
buy=prices[i];
}else{
res += prices[i]-buy;
buy=prices[i];
}
}
return res;
}
當我看了官方的解釋和代碼后多糠，真感覺自己智商被壓制了。其實做算法題就是做數(shù)學題浩考，關鍵是找到問題關鍵夹孔。下圖就是關鍵。
image.png
123. 買賣股票的最佳時機 III
利用狀態(tài)轉移方程（動態(tài)規(guī)劃）來解此題析孽。
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int[] dp = new int[5];
/*
j的5中狀態(tài)
j=0：不進行任何操作
j=1：第一次買入
j=2：第一次賣出
j=3：第二次買入
j=4：第二次賣出
*/
dp[1] = -prices[0];
dp[3] = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; i++) {
//以下計算為主邏輯搭伤，可以考慮將dp聲明為一位數(shù)組~~
dp[1] = Math.max(dp[1], -prices[i]);
dp[2] = Math.max(dp[2], prices[i] + dp[1]);
dp[3] = Math.max(dp[3], dp[2]-prices[i]);
dp[4] = Math.max(dp[4], prices[i] + dp[3]);
}
return Math.max(0, Math.max(dp[4], dp[2]));
}
