【LeetCode練習】[困難]123. 買賣股票的最佳時機 III
leetcode中還有
買賣股票的最佳時機I
買賣股票的最佳時機II
I,II 具體内容
123. 買賣股票的最佳時機 III
123. 買賣股票的最佳時機 III
算法思想:dp
題目:
leetcode官方解答
java代碼
class Solution {
public int maxProfit(int[] prices) {
int buy1 = -prices[0];
int buy2 = -prices[0];
int sell1 = 0;
int sell2 = 0;
for (int i = 1; i < prices.length; i++){
buy1 = Math.max(buy1,-prices[i]);
sell1 = Math.max(sell1,buy1+prices[i]);
buy2 = Math.max(buy2,sell1-prices[i]);
sell2 = Math.max(sell2,buy2+prices[i]);
}
return sell2;
}
}
123. 買賣股票的最佳時機 IV
123. 買賣股票的最佳時機 IV
算法思想:dp
題目:
java代碼
class Solution {
public int maxProfit(int k, int[] prices) {
if(k < 1){
return 0;
}
//交易次數過多,直接退化成, 任意交易次數,使得收益最大
if(k >= prices.length/2) {
return maxProfit2(prices);
}
//每一筆交易,有K*2個狀态
int[] buy = new int[k+1];//buy[i]:表示第i次買入
int[] sell = new int[k+1];//sell[i]:表示第i次賣出
Arrays.fill(buy, Integer.MIN_VALUE);//初始化
/**
* 高手解答:
* 借助股票問題,再次回扣一種極為普遍的dp定義: 考慮前XX種情況,滿足YY條件以及ZZ條件能夠達到的最值。
* 同時引申出,為什麼後邊要區分有沒有股票的情況,能不能不區分就把這個題做出來。
* 這道題我們不妨直接做這麼個定義:考慮前n支股票,最多交易k次能夠獲得的最大利潤。sell[k]
* 好了,基于這個定義,我們知道,最大利潤實際上就意味着手上不能有股票,否則就不叫最大利潤。
* 那麼不難推出下面這個dp的狀态轉移,這實際上還是基于0-1背包問題,即:賣不賣第i支股票。
*
* 1.如果不賣第i支股票,那麼很簡單,你既然不賣了,那我也不關心手裡有沒有股票了,
* 我可以考慮前i-1個股票最多賣k次,也就是sell[k]
* 2.如果你要賣第i支股票,那麼就比較複雜了,因為你得先有一隻股票,
* dp數組描述的是沒有股票的最值情況,是以你是不知道**有股票**的情況下,
* 考慮前i-1個股票,在最多賣k-1次的最大利潤的。
*/
/**
* 注意:
* 無論題目中是否允許「在同一天買入并且賣出」這一操作,
* 最終的答案都不會受到影響,這是因為這一操作帶來的收益為零。
* buy[],sell[]中存放的目前狀态中能帶來的最大收益
*/
for (int i = 0; i < prices.length; i++){//買入要看上一次賣出,賣出要有買入
for (int j = 1; j < k+1; j++){
buy[j] = Math.max(buy[j], sell[j-1]-prices[i]);//買入,要将之前的賣掉,sell[i-1]前一次賣出的最大收益
sell[j] = Math.max(sell[j], buy[j]+prices[i]);//賣出,之前買入的收益加上賣出股票價格
}
}
return sell[k];
}
public int maxProfit2(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++){
if (prices[i] > prices[i-1]){
maxProfit += prices[i]-prices[i-1];
}
}
return maxProfit;
}
}