☕ DSA Java Articles

Topics › Dynamic Programming › DP on Stocks

Best time to buy and sell stock

Medium TUF ID 301 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array prices where prices[i] is the price of one share of a stock on day i. You may complete at most one transaction: buy one share on some day and sell it on a strictly later day. Return the largest profit you can make. If every possible trade loses money, do not trade and return 0.

Constraints: 1 ≤ n ≤ 10^5, 0 ≤ prices[i] ≤ 10^4. The Java file also accepts an empty array and returns 0.

This is the first problem of the “DP on Stocks” family. The later problems (unlimited trades, at most two, at most k, cooldown, fee) all grow from the same question asked on every day: “if I sell today, what is the best day I could have bought?”

Example 1

prices = [7, 1, 5, 3, 6, 4]
answer = 5          // buy on day 1 at price 1, sell on day 4 at price 6

Example 2

prices = [7, 6, 4, 3, 1]
answer = 0          // prices only fall, so any trade loses money; we skip trading

Note that buying at 1 and “selling” at 7 is not allowed in Example 1, because day 0 comes before day 1. The order of days is the whole difficulty: the answer is not simply max - min.

Approach 1: Brute force

Intuition. A transaction is a pair of days (buy, sell) with buy < sell, and its profit is prices[sell] - prices[buy]. The answer is the largest profit over all such pairs, or 0 if they are all negative. Enumerating every pair is the definition turned into code. Starting best at 0 encodes the “do not trade” option, so losses are never reported.

Algorithm.

  1. Set best = 0.
  2. For every buy from 0 to n - 1, and every sell from buy + 1 to n - 1, update best with prices[sell] - prices[buy].
  3. Return best.
static int bruteForce(int[] prices) {
    int best = 0;
    for (int buy = 0; buy < prices.length; buy++) {
        for (int sell = buy + 1; sell < prices.length; sell++) {
            best = Math.max(best, prices[sell] - prices[buy]);
        }
    }
    return best;
}

Complexity. Time O(n^2): there are n(n-1)/2 pairs, each costing O(1). Space O(1).

With n = 10^5 that is about 5 × 10^9 pairs, far too slow. The waste is that for a fixed buy day we scan the whole future just to find its maximum, and we redo that scan for every buy.

Approach 2: Better, suffix maximum

Intuition. For a fixed buy day i, the best sell price is the largest price on any later day. That number does not depend on i in a complicated way: it is the maximum of the suffix prices[i..n-1]. All suffix maxima can be computed in one right-to-left sweep, because max(prices[i..n-1]) = max(prices[i], max(prices[i+1..n-1])). Then every buy day is answered in O(1).

Including day i itself in its own suffix is harmless: it only adds the profit 0 (buy and sell on the same day), and 0 is already the floor of the answer.

Algorithm.

  1. Build maxFrom[n - 1] = prices[n - 1], and for i from n - 2 down to 0, maxFrom[i] = max(prices[i], maxFrom[i + 1]).
  2. The answer is the maximum over i of maxFrom[i] - prices[i], floored at 0.
static int better(int[] prices) {
    int n = prices.length;
    if (n == 0) return 0;
    int[] maxFrom = new int[n];                         // maxFrom[i] = max(prices[i..n-1])
    maxFrom[n - 1] = prices[n - 1];
    for (int i = n - 2; i >= 0; i--) maxFrom[i] = Math.max(prices[i], maxFrom[i + 1]);
    int best = 0;
    for (int i = 0; i < n; i++) best = Math.max(best, maxFrom[i] - prices[i]);
    return best;
}

Complexity. Time O(n): two linear passes. Space O(n) for maxFrom.

This is already fast enough, but the extra array is unnecessary: the same information can be carried in one variable if we scan in the other direction.

Approach 3: Optimal, running minimum

Intuition. Flip the viewpoint. Instead of fixing the buy day and looking forward, fix the sell day i and look backward. The best buy for a sale on day i is the cheapest price on days 0..i. As we scan left to right, that cheapest price is a single number we can keep updating: minSoFar = min(minSoFar, prices[i]).

This is a one-dimensional DP in disguise. Define best(i) as the best profit using days 0..i only. Either the best trade sells before day i, giving best(i - 1), or it sells on day i, giving prices[i] - min(prices[0..i]). So best(i) = max(best(i - 1), prices[i] - minSoFar). Each state reads only the previous one, which is why two variables are enough.

Updating minSoFar before computing the profit means the same-day trade (profit 0) is considered, which again is harmless.

Algorithm.

  1. Set minSoFar = +∞ and best = 0.
  2. For each price p from left to right: minSoFar = min(minSoFar, p), then best = max(best, p - minSoFar).
  3. Return best.
static int optimal(int[] prices) {
    int minSoFar = Integer.MAX_VALUE, best = 0;
    for (int price : prices) {
        minSoFar = Math.min(minSoFar, price);           // cheapest buy on or before today
        best = Math.max(best, price - minSoFar);        // sell today
    }
    return best;
}

Dry run on prices = [7, 1, 5, 3, 6, 4]:

day price minSoFar price - minSoFar best
0 7 7 0 0
1 1 1 0 0
2 5 1 4 4
3 3 1 2 4
4 6 1 5 5
5 4 1 3 5

Complexity. Time O(n): one pass. Space O(1): two integers.

Why it is correct. Every valid trade has some sell day s. When the loop reaches s, minSoFar is the minimum over days 0..s, so the profit computed at s is at least the profit of that trade. Hence best is at least the optimum. And every value we compute corresponds to a real trade (buy at the minimum’s day, which is at or before s), so best never exceeds the optimum.

Connection to Kadane’s algorithm. Let d[i] = prices[i] - prices[i - 1]. The profit of buying on day a and selling on day b is d[a+1] + ... + d[b], a subarray sum. So this problem is “maximum subarray sum of the daily differences, floored at 0”, and the running-minimum loop is Kadane’s algorithm written in terms of prices instead of differences.

Edge cases and pitfalls