Best Time to Buy and Sell Stock in Rust

Given a list where prices[i] is a stock price on day i, choose one day to buy and a later day to sell. Return the largest possible profit, or zero when no profitable trade exists.

Start with the brute-force approach

The direct solution checks every possible buy-and-sell pair:

fn max_profit_slow(prices: &[i32]) -> i32 {
    let mut best = 0;

    for buy in 0..prices.len() {
        for sell in buy + 1..prices.len() {
            best = best.max(prices[sell] - prices[buy]);
        }
    }

    best
}

This is easy to understand, but it takes O(n²) time.

Track the cheapest price so far

When examining today's price, we only need two pieces of information:

The lowest price seen on an earlier day.
The best profit seen so far.

fn max_profit(prices: &[i32]) -> i32 {
    let mut cheapest = i32::MAX;
    let mut best = 0;

    for &price in prices {
        cheapest = cheapest.min(price);
        best = best.max(price - cheapest);
    }

    best
}

The algorithm visits each price once, giving O(n) time and O(1) additional space.

Verify the edge cases

#[test]
fn examples() {
    assert_eq!(max_profit(&[7, 1, 5, 3, 6, 4]), 5);
    assert_eq!(max_profit(&[7, 6, 4, 3, 1]), 0);
    assert_eq!(max_profit(&[]), 0);
}

The empty input works because the loop never runs. A descending list returns zero because every possible sale would lose money.