Best Time to Buy and Sell Stock II medium

Problem Statement

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

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

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

Steps

The key insight to solve this problem efficiently is to realize that we can accumulate profit by only considering the differences between consecutive days. If the price on day i+1 is greater than the price on day i, we can buy on day i and sell on day i+1 to make a profit. We don't need to worry about finding the absolute minimum and maximum prices because we can make multiple transactions.

  1. Initialize profit to 0. This variable will store our total profit.
  2. Iterate through the prices array: For each day i (except the last day), compare prices[i+1] with prices[i].
  3. If prices[i+1] > prices[i]: This means we can make a profit by buying on day i and selling on day i+1. Add the difference prices[i+1] - prices[i] to our profit.
  4. After the loop: The profit variable will hold the maximum profit achievable.

Explanation

This approach works because it cleverly exploits the fact that we can make as many transactions as we want. We don't need to find global minimums and maximums; we only care about local increases. Every time we find a price increase, we add that increase to our profit. This automatically accounts for all possible profitable trades.

Code (Java)

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i + 1] > prices[i]) {
                profit += prices[i + 1] - prices[i];
            }
        }
        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 to store the profit variable.