Domain 1EasyCORE

Best Time to Buy and Sell Stock II

The problem asks us to find the maximum profit that can be achieved from buying and selling stocks given an array of daily prices. We are allowed to make multiple transactions (buy and sell) but cannot hold more than one share at a time. The input is an array `prices` where each element represents the stock price on a particular day. The output should be the maximum profit possible.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Greedy

122. Best Time to Buy and Sell Stock II

Model: qwen2.5-coder:14b
Topics: Array,Greedy
FAANG asked: 1
Acceptance rate: 58.8%


Problem Breakdown

The problem asks us to find the maximum profit that can be achieved from buying and selling stocks given an array of daily prices. We are allowed to make multiple transactions (buy and sell) but cannot hold more than one share at a time. The input is an array prices where each element represents the stock price on a particular day. The output should be the maximum profit possible.

Inputs:

  • An array of integers prices, where each integer represents the stock price on a given day.

Outputs:

  • An integer representing the maximum profit that can be achieved.

Implicit Constraints or Tricky Edge Cases:

  • If the input array is empty, the maximum profit should be 0.
  • If all prices are in descending order, no transactions should be made, resulting in a profit of 0.
  • If all prices are in ascending order, buying at the start and selling at the end would yield the maximum profit.

Intuition

The brute-force approach involves checking every possible pair of days to determine if a transaction results in a profit. This approach has a time complexity of O(n^2), which is inefficient for large input sizes (up to 30,000 elements).

A better approach leverages the fact that we can accumulate profits from every upward trend in the stock prices. By iterating through the array and summing up all positive differences between consecutive days, we can achieve the maximum profit with a time complexity of O(n). This is because we are essentially capturing all profitable transactions.

Approach

  1. Initialize a variable max_profit to 0.
  2. Iterate through the prices array starting from the second element.
  3. For each day, if the price on that day is higher than the previous day’s price, add the difference to max_profit.
  4. Return max_profit.

This approach works because it captures all profitable transactions by summing up all positive differences between consecutive days.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the prices array. We iterate through the array once.
  • Space Complexity: O(1). We use a constant amount of extra space for storing the max_profit.

Solution

def maxProfit(prices):
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            max_profit += prices[i] - prices[i - 1]
    return max_profit

Edge Cases Handled

  • Empty Input: If the input array is empty, the loop does not execute, and max_profit remains 0.
  • Descending Prices: If all prices are in descending order, no positive differences will be added to max_profit, resulting in a profit of 0.
  • Ascending Prices: If all prices are in ascending order, the sum of all consecutive differences is calculated, yielding the maximum possible profit.