今日はケビンのアルゴリズムの旅の17日目です。リートコード問題122を解説し、「株の買い時・売り時」シリーズの強化版「株の買い時・売り時Ⅱ」を続けます。
すでに2つ書かれているので、知らない人はまずそれを読んできてください。
デイリースマイル
深い考え：何も決まっていません。
大きなことを何でも決められること。
問題 説明
i 番目の要素が i 日目の株価である配列が与えられます。
最大利益を計算するアルゴリズムを設計します。可能な限り多くの取引を成立させることができます。
注意：同時に複数の取引に参加することはできません。
例1.
入力：[7,1,5,3,6,4] 出力：7 解説：2日目に買い、3日目に売った場合、その取引の利益は = 5-1 = 4 です。続いて、4日目に買って5日目に売ると、利益は = 6-3 = 3 となります。例 2.
入力: [1,2,3,4,5] 出力: 4 解説: 1 日目に買って 5 日目に売れば、この取引で = 5-1 = 4 の利益が出ます。1日目と2日目に株を買って売ることはできないことに注意してください。これは、同時に複数の取引に参加することになり、株式を売却してから再度購入する必要があるためです。例 3.
入力: [7,6,4,3,1] 出力: 0 解説: この場合、取引は完了していないので、最大利益は 0 です。
問題解決
この質問に必要な条件はそれほど多くなく、凍結期間もありません。ただ、同時に複数の取引に関与できないことと、複数の購入で最大限の利益が得られることだけが条件です。
この問題を解く方法は他にもありますが、このアルゴリズムについての理解を深めるために、私は「動的計画法」を使うことにしました。
また、動的計画法については、今日紹介したコーホーのアルゴリズムに関する投稿をご覧ください。
ステップ1：状態の定義
状態dp[i][j]は次のように定義されます。
最初の次元 i は、i で示される日に得られる最大利益を示し、2 番目の次元 j は、i で示される日に株式が保有されていないか、保有されているかを示します。2次元目のjは、iで指数付けされた日に株式が保有されていないか、または保有されているかを示します。
ステップ2：状態遷移方程式
- 非保有から始まり、最終日時点でも非保有のままです；
- 毎日、状態を変更したり、そのままにしたりすることができます。
ステップ3：初期設定
- 何もしなければdp[0][0]=0；
- つまり、dp[0][1] = -prices[i]となります；
ステップ4：リターンバリュー
dp[0][0] = 0終了時には、dp[len - 1][0] を出力します。
コードの実装
//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 < length; 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 < len; i++) {
// この2行の順番を入れ替えても構わない。
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を通して実行されました！
チャッターボックスにて
多くの人が良い習慣を身につけたいと願っていますが、ほとんどの人は3分間人間です。そのため、次のような計画を立てることにしました。
一緒にアルゴリズムを学び、ボーナスを受け取ってください！
参加方法：
また、多くの友人と「会う」こともできます。
団結し、共に学び、共に向上すること！
パンチカードのルールは
報酬
連続出勤1日につき $6.60の レッドパケットを私にご連絡ください！
連続出勤1日ごとに $16.60の レッドパケットをお渡しします！
66.60ドルの レッドパケットをご希望の方はご連絡ください！
