122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the i-th day.

On each day, you may choose to buy and/or sell the stock. You can hold at most one share at a time. However, you can buy it again after selling it.

Return the maximum profit you can achieve.

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 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 3.
Total profit = 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 = 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: No transaction is done.

Constraints:

1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

Solution

Key Idea

The problem allows multiple transactions, but you can only hold one share at a time. The best way to maximize profit is to sum up every positive price difference between consecutive days.

If prices go up from one day to the next, we simulate buying yesterday and selling today to capture the gain.

Step-by-Step Example

Input: prices = [7,1,5,3,6,4]

Day 1 to Day 2: price drop, do nothing.
Day 2 to Day 3: +4 profit (buy at 1, sell at 5)
Day 3 to Day 4: price drop, do nothing.
Day 4 to Day 5: +3 profit (buy at 3, sell at 6)
Day 5 to Day 6: price drop, do nothing.

Total profit = 4 + 3 = 7.

Complexity Analysis

Time Complexity: O(n)
Single pass through the price list.

Space Complexity: O(1)
Only one variable to store profit.

Java Solution:

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;
    }
}

Kotlin Solution:

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var profit = 0
        for (i in 1 until prices.size) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1]
            }
        }
        return profit
    }
}

Scala Solution:

object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        var profit = 0
        for (i <- 1 until prices.length) {
            if (prices(i) > prices(i - 1)) {
                profit += prices(i) - prices(i - 1)
            }
        }
        profit
    }
}

JavaScript Solution:

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

TypeScript Solution:

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

Solution​

Solution