Best Time to Buy and Sell Stock II

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the ith 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.

Examples

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.

Example 3:

Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Approaches

1. Simple Approach (Peak Valley Approach)

This approach involves identifying local minima and maxima, and summing up the differences.

Time Complexity: O(n), where n is the number of days Space Complexity: O(1)

2. Optimal Approach (One Pass)

The optimal approach uses a single pass through the array, adding up all the positive price differences.

Time Complexity: O(n) Space Complexity: O(1)

Solutions

Java Solution

// Simple Approach (Peak Valley Approach)
class Solution {
    public int maxProfit(int[] prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;
        while (i < prices.length - 1) {
            while (i < prices.length - 1 && prices[i] >= prices[i + 1])
                i++;
            valley = prices[i];
            while (i < prices.length - 1 && prices[i] <= prices[i + 1])
                i++;
            peak = prices[i];
            maxprofit += peak - valley;
        }
        return maxprofit;
    }
}

// Optimal Approach (One Pass)
class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

C++ Solution

// Simple Approach (Peak Valley Approach)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;
        while (i < prices.size() - 1) {
            while (i < prices.size() - 1 && prices[i] >= prices[i + 1])
                i++;
            valley = prices[i];
            while (i < prices.size() - 1 && prices[i] <= prices[i + 1])
                i++;
            peak = prices[i];
            maxprofit += peak - valley;
        }
        return maxprofit;
    }
};

// Optimal Approach (One Pass)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
};

Explanation

Simple Approach (Peak Valley Approach)

Identify "valleys" (local minima) and "peaks" (local maxima) in the price sequence.
For each pair of adjacent valley and peak, calculate the profit.
Sum up all these profits.

This approach simulates the process of buying at each valley and selling at each peak.

Optimal Approach (One Pass)

This approach is based on the observation that the sum of all positive price differences is equal to the maximum profit we can obtain.

Iterate through the prices starting from the second day.
If the current price is higher than the previous day's price, add the difference to the total profit.

This method is more efficient and simpler to implement than the Peak Valley approach, while yielding the same result.

Test Cases

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.
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.
Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Input: prices = [3,3,5,0,0,3,1,4] Output: 8 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3. Finally, buy on day 2 (price = 3) and sell on day 3 (price = 5), profit = 5-3 = 2. Total profit is 3 + 3 + 2 = 8.

These test cases cover scenarios with multiple buy-sell opportunities, consistently increasing prices, consistently decreasing prices, and a mix of trends including repeated prices.

Best Time to Buy and Sell Stock

Jump Game