Best Time to Buy and Sell Stock II

NeetCode: Best Time to Buy and Sell Stock II · LeetCode: 122. Best Time to Buy and Sell Stock II · Difficulty: Medium

You are given an array prices where prices[i] is the price of a stock on day i. You may buy and sell as many times as you like, but you can hold at most one share at a time (you must sell before buying again; buying and selling on the same day is allowed). Return the maximum profit.

Example

Text

Input:  prices = [7, 1, 5, 3, 6, 4]    Output: 7   (buy at 1, sell at 5, buy at 3, sell at 6)
Input:  prices = [1, 2, 3, 4, 5]       Output: 4
Input:  prices = [7, 6, 4, 3, 1]       Output: 0

Brute force: try every buy/sell decision

On each day the trader either holds a share or not. Without a share, they can buy (pay prices[i]) or wait; with one, they can sell (gain prices[i]) or wait. Trying every choice on every day gives 2^n action sequences.

Java

class Solution {
    public int maxProfit(int[] prices) {
        return go(prices, 0, false);
    }

    private int go(int[] p, int day, boolean holding) {
        if (day == p.length) {
            return 0;
        }
        int wait = go(p, day + 1, holding);
        if (holding) {
            return Math.max(wait, p[day] + go(p, day + 1, false));
        }
        return Math.max(wait, -p[day] + go(p, day + 1, true));
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(s.maxProfit(new int[]{1, 2, 3, 4, 5}));
        System.out.println(s.maxProfit(new int[]{7, 6, 4, 3, 1}));
        System.out.println(s.maxProfit(new int[]{}));
    }
}

Output

Time: O(2^n). Space: O(n) recursion depth. Each call uses stack space, so this version is only safe for small n.

Better: DP over (day, holding)

The recursion only has 2n distinct states, (day, holding). Two running int values replace a table: cash is the best profit while holding nothing, hold is the best profit while holding a share. Each day: cash = max(cash, hold + price) and hold = max(hold, cash_before - price).

Java

class Solution {
    public int maxProfit(int[] prices) {
        int cash = 0;
        int hold = Integer.MIN_VALUE / 2; // stands in for -infinity: "holding" is impossible before the first buy
        for (int p : prices) {
            int newCash = Math.max(cash, hold + p);
            int newHold = Math.max(hold, cash - p);
            cash = newCash;
            hold = newHold;
        }
        return cash;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(s.maxProfit(new int[]{1, 2, 3, 4, 5}));
        System.out.println(s.maxProfit(new int[]{7, 6, 4, 3, 1}));
        System.out.println(s.maxProfit(new int[]{}));
    }
}

Output

Time: O(n). Space: O(1).

Optimal: greedy, collect every rise

Any profitable trade over several days equals the sum of the day-to-day increases in between: buying at 1 and selling at 6 over 1, 5, 3, 6 gains 5, which is (5-1) + (6-3) once the dip 5 -> 3 is skipped. So the answer is the sum of every positive difference prices[i] - prices[i-1], ignoring the drops. Each gain can be taken independently of the others, which is why the greedy choice is safe.

Java

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            profit += Math.max(prices[i] - prices[i - 1], 0);
        }
        return profit;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(s.maxProfit(new int[]{1, 2, 3, 4, 5}));
        System.out.println(s.maxProfit(new int[]{7, 6, 4, 3, 1}));
        System.out.println(s.maxProfit(new int[]{}));
    }
}

Output

Time: O(n). Space: O(1).

The DP and the greedy are both linear. The DP form generalises to variants with a fee or a cooldown, where the greedy no longer applies directly. The greedy loop starts at index 1, so it does not run for empty or single-day arrays, and both return 0.

The starting value of hold is Integer.MIN_VALUE / 2. It only has to be far below any real profit, and half the minimum leaves room to add prices without leaving the int range. The constraints (at most 30,000 prices, each at most 10,000) keep every real sum inside int; Java int arithmetic wraps silently on overflow.