algoadvance

You are given an integer array prices where prices[i] is the price of a given stock on the ( i )-th day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

• Input: ([7,1,5,3,6,4])
• Output: 7
• Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.

Example 2:

• Input: ([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. Total profit is 4.

Example 3:

• Input: ([7,6,4,3,1])
• Output: 0
• Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• ( 1 \leq prices.length \leq 3 * 10^4 )
• ( 0 \leq prices[i] \leq 10^4 )

Clarifying Questions

• Can the prices array be empty or have only one element?
  • According to the constraints, the array will always have at least one element.

Strategy

To maximize profit, you want to take advantage of all price rises. You can achieve this by adding up all positive differences between consecutive days. Thus, the strategy is:

• Traverse the array from the start.
• For each day, if the next day’s price is higher than the current day’s price, add the difference to the total profit.
• Return the accumulated profit at the end.

This greedy strategy works because any accumulated positive differences will represent profitable transactions.

Code

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

# Example Usage
print(maxProfit([7, 1, 5, 3, 6, 4]))  # Output: 7
print(maxProfit([1, 2, 3, 4, 5]))     # Output: 4
print(maxProfit([7, 6, 4, 3, 1]))     # Output: 0

Time Complexity

The time complexity of this algorithm is ( O(n) ), where ( n ) is the length of the prices array. This is because the solution involves a single pass through the array, making comparisons and additions for each day.

Space Complexity

The space complexity is ( O(1) ), as we are only using a constant amount of extra space for the total profit variable.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?