122. Best Time to Buy and Sell Stock II

Intuition

The goal is to maximize profit by taking advantage of daily price differences. Since you can buy and sell on the same day, the problem can be reduced to summing up all positive differences between consecutive prices. This approach ensures that you capture all profitable opportunities.

Approach

1. Initialize maxProfit to 0.
2. Iterate through the array starting from the second price: - For each price, if it is higher than the previous day's price, add the difference to maxProfit.
3. Return maxProfit.

This approach works because it effectively buys on every local minimum and sells on every local maximum, capturing all profitable transactions.

Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array. This is because we iterate through the array once.

Space Complexity

The space complexity is O(1) since we are using only a single additional variable to keep track of the profit.

Code

C++

class Solution {
public:
    int maxProfit(vector& 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;
    }
};

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxProfit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                maxProfit += prices[i] - prices[i - 1]
        return maxProfit

Java

class Solution {
    public int maxProfit(int[] prices) {
        int price = prices[0];
        int maxProfit = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > price ) {
                maxProfit += prices[i] - price;
            }
            
            price = prices[i];
            

        }
        return maxProfit;
    }
}

JavaScript

function maxProfit(prices) {
    let maxProfit = 0
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            maxProfit += prices[i] - prices[i - 1]
        }
    }
    return maxProfit
}