Back to solutions

Best Time to Buy And Sell Stock II

MediumArrays

Maximize profit with unlimited buy/sell transactions.

Open problem
Constraints
  • 1 <= n <= 3*10^4
  • 0 <= prices[i] <= 10^4

Sum every upward step

Time O(n)Space O(1)

With unlimited transactions, the best total profit is the sum of every positive day-to-day increase. Capturing each rise prices[i] - prices[i-1] when it is positive is equivalent to buying before each climb and selling at the top.

Key terms
transaction:
One buy followed by a later sell of the single share you may hold.
upward step:
A consecutive pair where the price rises; its gain can always be captured.
int maxProfit(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];
    return profit;
}
Step by step
  1. Set profit = 0.
  2. For each adjacent pair, if today's price exceeds yesterday's, add the difference.
  3. Summing all rises equals the optimal multi-transaction profit.