Go 刷 leetcode｜繼續(xù)買股票？

今天為大家講解 LeetCode 第 122 題，繼續(xù)為大家?guī)怼纲I賣股票」系列的其中一個提升版《買賣股票的最佳時機 II》。

已經(jīng)寫了兩篇，建議不了解的朋友先去看看～?

leetcode｜割韭菜的最佳時機

leetcode｜割冷凍韭菜的最佳時機

題目描述

給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入: [7,1,5,3,6,4] 輸出: 7 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。示例 2:

輸入: [1,2,3,4,5] 輸出: 4 解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。示例 3:

輸入: [7,6,4,3,1] 輸出: 0 解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii 著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解題思路

這題的要求其實并不多，沒有凍結期，只要求不能同時參與多筆交易，多次購買的最大利潤。

這道題有其他方法可以解決，但我仍然選擇使用「動態(tài)規(guī)劃」，繼續(xù)加強大家對此算法的理解。

另外，關于動態(tài)規(guī)劃可以看我今天分享的小浩算法的那篇文章。

同樣的，第一步：定義狀態(tài)

狀態(tài) dp[i][j] 定義如下

第一維 i 表示索引為i的那一天（具有前綴性質，即考慮了之前天數(shù)的收益）能獲得的最大利潤；第二維 j表示索引為i 的那一天是未持有股票，還是持有股票。這里 0 表示未持有股票，1 表示持有股票。

第二步：狀態(tài)轉移方程

• 狀態(tài)從未持有股票開始，到最后一天我們關心的狀態(tài)依然是未持有股票；
• 每一天狀態(tài)可以轉移，也可以不動。

第三步：初始化（base case）

• 如果什么都不做，dp[0][0] = 0；
• 如果買入股票，當前收益是負數(shù)，即 dp[0][1] = -prices[i]；

第四步：返回值

終止的時候，輸出 dp[len - 1][0]，因為一定有 dp[len - 1][0]（賣了未持股） > dp[len - 1][1]（持股）。

代碼實現(xiàn)

//go
func?maxProfit(prices?[]int)?int?{
????length?:=?len(prices)
????if?length?2?{
????????return?0
????}
????dp?:=?make([][2]int,?length)

????dp[0][0]?=?0
????dp[0][1]?=?-prices[0]

????for?i?:=?1;?i?????????dp[i][0]?=?max(dp[i-1][0],?dp[i-1][1]+prices[i])
????????dp[i][1]?=?max(dp[i-1][1],?dp[i-1][0]-prices[i])
????}

????return?dp[length-1][0]

}

func?max(x,?y?int)?int?{
????if?x?>?y?{
????????return?x
????}
????return?y
}

//java
public?class?Solution?{

????public?int?maxProfit(int[]?prices)?{
????????int?len?=?prices.length;
????????if?(len?2)?{
????????????return?0;
????????}

????????//?0：未持有股票
????????// 1：持有股票
????????int[][]?dp?=?new?int[len][2];

????????dp[0][0]?=?0;
????????dp[0][1]?=?-prices[0];

????????for?(int?i?=?1;?i?????????????//?這兩行調換順序也是可以的
????????????dp[i][0]?=?Math.max(dp[i?-?1][0],?dp[i?-?1][1]?+?prices[i]);
????????????dp[i][1]?=?Math.max(dp[i?-?1][1],?dp[i?-?1][0]?-?prices[i]);
????????}
????????return?dp[len?-?1][0];
????}
}

鄭重聲明：

所展示代碼已通過 LeetCode 運行通過，請放心食用～