Best Time to Buy And Sell Stock II

Problem Description

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

Constraints

• 1 <= prices.length <= 3 * 10⁴
• 0 <= prices[i] <= 10⁴

Accumulating Positive Increments Greedily

While you cannot hold multiple shares of stock simultaneously, you can make transactions on consecutive days. If price increases from day i-1 to day i, you can buy on day i-1 and sell on day i. The total profit is equivalent to the sum of all consecutive upward price slopes. By accumulating every positive price difference between adjacent days, you capture all profitable steps.

Solution 1: Greedy Slope Accumulation

Iterate through the prices array and sum all positive differences between successive days.

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]; // accumulate positive steps
            }
        }
        return profit;
    }
}

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]  # accumulate positive steps
        return profit

#include <vector>

class Solution {
public:
    int maxProfit(std::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]; // accumulate positive steps
            }
        }
        return profit;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we iterate through the price history once.
• Space Complexity: O(1) auxiliary space as we only use a primitive accumulator variable.

Where It Breaks

This greedy approach requires complete and immediate liquidity, assuming transaction fees are zero. If transaction fees exist (e.g. Best Time to Buy and Sell Stock with Transaction Fee), this model fails because buying and selling every day to capture micro-increases would drain profits.

Common Mistakes

• Incorrect index bounds: Beginning the loop at i = 0 and comparing with i - 1, causing an index out of bounds error.
• Tracking min/max manually: Attempting to use complex local peak-valley tracking states instead of accumulating the slopes directly.

Frequently Asked Questions

Can we execute multiple trades on the same day? Yes, but since you can only hold one share at a time, buying and selling on the same day yields a net change of zero.

How does this differ from Buy and Sell Stock I? In Buy and Sell Stock I, you are only allowed to make a single transaction (one buy, one sell). In this version, you can execute as many transactions as you like.

← All Problems