[LeetCode] 0123. Best Time to Buy and Sell Stock III

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

內容目錄

Hard

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

Python

				
					# time complexity: O(n)
# space complexity: O(n)
from typing import List


class Solution(object):
    def maxProfit(self, prices: List[int]) -&gt; int:
        if len(prices) &lt;= 1:
            return 0

        leftMin = prices[0]
        rightMax = prices[-1]

        length = len(prices)
        leftProfits = [0] * length
        rightProfits = [0] * (length + 1)

        for l in range(1, length):
            leftProfits[l] = max(leftProfits[l - 1], prices[l] - leftMin)
            leftMin = min(leftMin, prices[l])

            r = length - 1 - l
            rightProfits[r] = max(rightProfits[r + 1], rightMax - prices[r])
            rightMax = max(rightMax, prices[r])

        maxProfit = 0
        print(leftProfits)
        print(rightProfits)
        for i in range(0, length):
            maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i + 1])

        return maxProfit


prices = [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))

Hard

Python

相關文章