[LeetCode Solution] 122. Best Time to Buy and Sell Stock II

Problem Description

Best Time to Buy and Sell Stock II

Calculate the maximum profit that can be obtained by buying and selling stocks multiple times. Unlike Best Time to Buy and Sell Stock, this problem allows multiple transactions of buying and selling.

Solution

Approach

This problem can be easily solved by visualizing the list as a graph. If we represent it as a stock graph, we can catch the turning points and accumulate the profit.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = prices[0]     # Set the first price as the lowest price
        before = prices[0]  # Initialize the previous price
        acc = 0             # Initialize the cumulative profit

        # Iterate through prices
        for v in prices:
            # If the current price is greater than or equal to the previous price, continue
            if before <= v:
                before = v
                continue

            # If the current price is less than the previous price, update the cumulative profit and set the lowest and previous prices to the current price
            acc += before - low
            before = low = v

        # Update the cumulative profit for the last remaining part
        acc += before - low
        return acc

The time complexity and space complexity of this solution are as follows:

• Time Complexity: O(N)
  • As the loop iterates through prices, the time complexity is O(N).
• Space Complexity: O(1)
  • No additional space is used.