123. Best Time to Buy and Sell Stock III

Problem Statement

link: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/ https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/

You are given an array prices where prices[i] is the price of a given stock on the ith 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:

Input: prices = [3,3,5,0,0,3,1,4] Output: 6

Input: prices = [1,2,3,4,5] Output: 4

Input: prices = [7,6,4,3,1] Output: 0

Solution Approach

The problem is tackled by utilizing dynamic programming to keep track of the profit after each buy and sell action over two transactions.

Algorithm

1. Initialization: Set four variables buy1, sell1, buy2, and sell2 to track profits for two transactions.
2. Iteration: For each price, update the buy and sell variables by comparing their previous values with potential profit scenarios.
3. Result: The final profit after two transactions is stored in sell2.

Implement

    # buy1[i] = max(buy1[i - 1], -prices[i]) # sell1[i] = max(sell1[i - 1], buy1[i] + prices[i]) # buy2[i] = max(buy2[i - 1], sell1[i] - prices[i]) # sell2[i] = max(sells[i - 1], buy2[i] + prices[i]) class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        sell1 = sell2 = 0
        buy1 = buy2 = -float('inf')
        for p in prices:
            buy1 = max(buy1, -p)
            sell1 = max(sell1, buy1 + p)
            buy2 = max(buy2, sell1 - p)
            sell2 = max(sell2, buy2 + p)
        return sell2

    
    

Twitter  facebook  Email