[LeetCode] 0123. 株式の売買に最適な時期 III

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

難しい

配列が与えられます 価格 どこ 価格[i] は、特定の株式の価格です。 ^私は 日。

達成できる最大の利益を見つけてください。 最大で 2 つのトランザクション.

注記： 同時に複数の取引を行うことはできません（つまり、株式を再度購入する前に売却する必要があります）。

例 1:

入力： 価格 = [3,3,5,0,0,3,1,4]
出力： 6
説明： 4 日目に購入 (価格 = 0)、6 日目に売却 (価格 = 3)、利益 = 3-0 = 3。その後、7 日目に購入 (価格 = 1)、8 日目に売却 (価格 = 4)、利益= 4-1 = 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 となります。

制約:

1 <= 価格.長さ <= 10 ⁵
0 <= 価格[i] <= 10 ⁵

パイソン

				
					# 時間計算量: O(n) # 空間計算量: 入力による O(n) import リスト クラス Solution(object): def maxProfit(self, 価格: List[int]) -> int: if len(prices) <= 1 : 0 を返します leftMin = 価格[0] rightMax = 価格[-1] length = len(価格) leftProfits = [0] * 長さ rightProfits = [0] * (length + 1) for l in range(1, length): leftProfits[l] = max(leftProfits[l - 1], 価格[l] - leftMin) leftMin = min(leftMin, 価格[l]) r = 長さ - 1 - l rightProfits[r] = max(rightProfits[r + 1]、rightMax - 価格[r]) rightMax = max(rightMax, 価格[r]) maxProfit = 0 print(leftProfits) print(rightProfits) for i in range(0, length): maxProfit = max(maxProfit, leftProfits[ i] + rightProfits[i + 1]) maxProfit 価格を返す = [7, 1, 5, 3, 6, 4] # leftProfit = [0, 0, 4, 4, 5, 5] # rightProfit = [5, 5] 、3、3、0、0、0] print(Solution().maxProfit(prices))

難しい

パイソン

関連記事