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
- Initialize a variable
max_profitto 0. - Iterate through the
pricesarray starting from the second element. - For each day, if the price on that day is higher than the previous day’s price, add the difference to
max_profit. - 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
pricesarray. 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_profitremains 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.