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 i^th 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 only need to consider the differences between consecutive days' prices. If the price on day i+1 is greater than the price on day i, we can buy on day i and sell on day i+1 to make a profit. We can do this repeatedly for all such pairs.

1. Iterate: Iterate through the prices array from the second element (index 1).
2. Compare: For each element, compare it with the previous element.
3. Accumulate Profit: If the current element is greater than the previous element, add the difference to the total profit.
4. Return Profit: After iterating through the entire array, return the total accumulated profit.

Explanation

This approach works because it captures all possible profitable transactions. We don't need to track individual buy and sell points explicitly. The algorithm only adds the profit when a price increase is observed, thus capturing the maximum profit possible by exploiting all price rises. This avoids the need for complex dynamic programming or other optimization strategies.

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (size_t i = 1; i < prices.size(); ++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.