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 to solving this problem efficiently is to realize that we can accumulate profit by identifying all the peaks and valleys in the price array. We don't need to find the absolute minimum and maximum; instead, we simply look for opportunities where the price increases from one day to the next. The total profit is the sum of all these individual gains.

1. Iterate through the prices: We'll traverse the prices array from left to right.
2. Identify price increases: For each day, we check if the price is higher than the price on the previous day.
3. Accumulate profit: If the price is higher, we add the difference (the profit) to our total profit.

Explanation:

This approach is greedy because at each step, we are making the locally optimal choice (selling when the price increases). It's proven that this greedy approach yields the globally optimal solution for this problem. We are essentially summing up all the positive differences between consecutive days. This approach avoids the need for complex dynamic programming or other advanced algorithms.

Code:

def maxProfit(prices):
    """
    Calculates the maximum profit from stock transactions.

    Args:
        prices: A list of stock prices on consecutive days.

    Returns:
        The maximum profit achievable.
    """
    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

Complexity:

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