Pular para o conteúdo principal

Best Time to Buy and Sell Stock II

You are given the list of prices of a particular stock. Each element in the array represents the price of the stock at a given second throughout the current day. Return the maximum profit you can make trading this stock.

Note: You may only ever buy and sell a single share of the stock, but you may make multiple transactions (i.e. buys and sells).

Example(s)​

Example 1:

Input: prices = [8, 3, 2, 4, 6, 4, 5]
Output: 5
Explanation:
- Buy at 2, sell at 4: profit = 2
- Buy at 4, sell at 6: profit = 2
- Buy at 4, sell at 5: profit = 1
Total profit = 2 + 2 + 1 = 5

Example 2:

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7
Explanation:
- Buy at 1, sell at 5: profit = 4
- Buy at 3, sell at 6: profit = 3
Total profit = 4 + 3 = 7

Example 3:

Input: prices = [1, 2, 3, 4, 5]
Output: 4
Explanation:
- Buy at 1, sell at 2: profit = 1
- Buy at 2, sell at 3: profit = 1
- Buy at 3, sell at 4: profit = 1
- Buy at 4, sell at 5: profit = 1
Total profit = 1 + 1 + 1 + 1 = 4
(Or simply: buy at 1, sell at 5: profit = 4)

Example 4:

Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation:
Prices are always decreasing, so no profit can be made.

Solution​

The solution uses a greedy approach:

Key Insight: Since we can make multiple transactions, we should capture every price increase. The maximum profit is achieved by buying before every price increase and selling right after.

Strategy: Sum up all positive differences between consecutive prices. If prices[i+1] > prices[i], we can make a profit of prices[i+1] - prices[i] by buying at i and selling at i+1.

JavaScript Solution

/**
* Calculate maximum profit from multiple stock transactions
* @param {number[]} prices - Array of stock prices
* @return {number} - Maximum profit
*/
function maxProfit(prices) {
let profit = 0;

// Iterate through prices, looking for price increases
for (let i = 1; i < prices.length; i++) {
  // If price increased, add the profit
  if (prices[i] > prices[i - 1]) {
    profit += prices[i] - prices[i - 1];
  }
}

return profit;
}

// Test cases
console.log('Example 1:', maxProfit([8, 3, 2, 4, 6, 4, 5])); // 5
console.log('Example 2:', maxProfit([7, 1, 5, 3, 6, 4])); // 7
console.log('Example 3:', maxProfit([1, 2, 3, 4, 5])); // 4
console.log('Example 4:', maxProfit([7, 6, 4, 3, 1])); // 0
console.log('Test 5:', maxProfit([1, 2, 3, 2, 1])); // 2
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (More Explicit)​

Here's a more explicit version that shows the buy/sell transactions:

/**
 * Alternative: More explicit version showing transactions
 */
function maxProfitExplicit(prices) {
  let profit = 0;
  let buyPrice = null;
  
  for (let i = 0; i < prices.length; i++) {
    if (buyPrice === null) {
      // Look for buying opportunity (price will increase next)
      if (i < prices.length - 1 && prices[i + 1] > prices[i]) {
        buyPrice = prices[i];
      }
    } else {
      // Look for selling opportunity (price will decrease next or at end)
      if (i === prices.length - 1 || prices[i + 1] < prices[i]) {
        profit += prices[i] - buyPrice;
        buyPrice = null;
      }
    }
  }
  
  return profit;
}

Complexity​

  • Time Complexity: O(n) - Where n is the length of the prices array. We iterate through the array once.
  • Space Complexity: O(1) - We only use a constant amount of extra space.

Approach​

The solution uses a greedy strategy:

  1. Key insight: Since we can make multiple transactions, we should capture every price increase
  2. Simple strategy: For each consecutive pair of prices, if the price increases, we can profit from it
  3. Sum all profits: Add up all positive differences between consecutive prices
  4. Optimal: This approach is optimal because:
    • We capture every possible profit opportunity
    • We don't miss any price increases
    • We don't hold stocks unnecessarily

Why This Works​

Mathematical proof:

  • If we have prices [a, b, c] where a < b < c:

    • Strategy 1: Buy at a, sell at c: profit = c - a
    • Strategy 2: Buy at a, sell at b, then buy at b, sell at c: profit = (b - a) + (c - b) = c - a
    • Both strategies yield the same profit!

  • Therefore, we can break down any long transaction into multiple short transactions without losing profit

  • The greedy approach (capture every increase) is equivalent to the optimal strategy

Key Insights​

  • Greedy approach works: Capturing every price increase is optimal
  • Multiple transactions: We can break down long transactions into shorter ones
  • Simple solution: Just sum all positive differences
  • No need for DP: Unlike the single-transaction version, we don't need dynamic programming
  • O(n) time: Single pass through the array is sufficient

Step-by-Step Example​

Let's trace through Example 1: prices = [8, 3, 2, 4, 6, 4, 5]

Prices: [8, 3, 2, 4, 6, 4, 5]
         ↓  ↓  ↓  ↓  ↓  ↓  ↓
Indices: 0  1  2  3  4  5  6

Compare consecutive prices:
- prices[1] - prices[0] = 3 - 8 = -5 (decrease, skip)
- prices[2] - prices[1] = 2 - 3 = -1 (decrease, skip)
- prices[3] - prices[2] = 4 - 2 = +2 (increase, add to profit)
  profit = 2
- prices[4] - prices[3] = 6 - 4 = +2 (increase, add to profit)
  profit = 2 + 2 = 4
- prices[5] - prices[4] = 4 - 6 = -2 (decrease, skip)
- prices[6] - prices[5] = 5 - 4 = +1 (increase, add to profit)
  profit = 4 + 1 = 5

Final profit = 5

Visual Representation​

Prices: [8, 3, 2, 4, 6, 4, 5]
         ↓  ↓  ↓  ↑  ↑  ↓  ↑
                    ↑     ↑
                    ↑     ↑
              Profit: 2   1
                    ↑
              Profit: 2

Total: 2 + 2 + 1 = 5

Edge Cases​

  • Empty array: Return 0
  • Single price: Return 0 (can't make a transaction)
  • Always decreasing: Return 0 (no profit possible)
  • Always increasing: Return prices[n-1] - prices[0]
  • All same prices: Return 0 (no profit)

Comparison with Single Transaction Version​

Best Time to Buy and Sell Stock I (single transaction):

  • Can only buy and sell once
  • Requires tracking minimum price and maximum profit
  • More complex: O(n) time, O(1) space

Best Time to Buy and Sell Stock II (multiple transactions):

  • Can buy and sell multiple times
  • Simple greedy: sum all positive differences
  • Simpler: O(n) time, O(1) space
  • Best Time to Buy and Sell Stock I: Single transaction
  • Best Time to Buy and Sell Stock III: At most 2 transactions
  • Best Time to Buy and Sell Stock IV: At most k transactions
  • Best Time to Buy and Sell Stock with Cooldown: With cooldown period
  • Best Time to Buy and Sell Stock with Transaction Fee: With transaction fee

Takeaways​

  • Greedy approach is optimal when we can make unlimited transactions
  • Capture every increase is the key strategy
  • Simple solution - no need for complex algorithms
  • Multiple transactions can be broken down into consecutive pairs
  • O(n) single pass is optimal for this problem