[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

Table of contents

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 (ie, 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, ie 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]) -> int: if len(prices) <= 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

related articles