Best Time to Buy and Sell Stock II medium

Problem Statement

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 as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [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: prices = [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.

Steps

The key insight to solve this problem efficiently is to realize that we can make a profit whenever the price on a given day is higher than the price on the previous day. We don't need to track individual buy and sell points; we only need to sum up all the price differences where the current price exceeds the previous price.

  1. Initialize profit: Start with a total profit of 0.
  2. Iterate through prices: Iterate through the prices array starting from the second element (index 1).
  3. Calculate profit for each day: For each day, compare the current price with the previous day's price. If the current price is higher, add the difference to the total profit.
  4. Return total profit: After iterating through all the prices, return the accumulated total profit.

Explanation

This approach leverages the fact that we can perform unlimited transactions. Instead of finding optimal buy and sell points, we simply accumulate the profit from all upward price movements. This avoids the complexity of exploring all possible buy/sell combinations. The algorithm's efficiency comes from its linear time complexity.

Code

public class Solution {
    public int MaxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.Length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

Complexity

  • Time Complexity: O(n), where n is the length of the prices array. We iterate through the array once.
  • Space Complexity: O(1). We only use a constant amount of extra space to store the profit variable.