LESSON 350 OF 414 · DYNAMIC PROGRAMMING

Best Time to Buy and Sell Stock in Rust: O(k * n) With a Running Best

Practice O(n²) Read the full explanation

Say you have an array prices for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

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

Example 1:

Input: prices = [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: prices = [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

STEP 1 OF 8

Guided

Ctrl + Enter to check

RUST · DYNAMIC PROGRAMMING

Best Time To Buy Stock in Rust, explained

Problem overview

The function max_profit receives a vector of daily prices and a limit k on the number of transactions. Each transaction is a buy followed by a later sell, and you may hold at most one purchase at a time. The function returns the largest total profit.

For prices = [3, 2, 6, 5, 0, 3] and k = 2 the answer is 7: buy at 2 and sell at 6 for 4, then buy at 0 and sell at 3 for 3. For [2, 4, 1] the answer is 2, from a single transaction.

Approach: replace the buy-day scan with a running maximum

The table is the same as in the slower solution. dp[t][i] is the best profit using at most t transactions in the first i days. The slower solution found the sale on day i by trying every earlier buy day j, which costs O(n) per cell and O(k * n²) overall.

Look at what that scan computes. For a sale on day i after a buy on day j, the total is

dp[t - 1][j - 1] + prices[i - 1] - prices[j - 1]

The price of day i is the same for every j, so only the part that depends on j matters: dp[t - 1][j - 1] - prices[j - 1]. The best sale on day i is that part's maximum over all earlier buy days, plus the current price. And that maximum changes by only one candidate per day, so it can be kept in a variable and updated as i moves forward. This running best is max_diff, and it turns the inner loop into constant work.

Row t - 1 is complete before row t starts, so its values can be read freely. The buy candidate for day i is dp[t - 1][i] - prices[i - 1]: the best profit from t - 1 transactions over the first i days, minus today's price. Using the first i days rather than the first i - 1 is fine: it amounts to selling and buying again on the same day, which changes nothing, since the profit counts the same as holding on.

Step by step

Store the length in n and rebind k as a usize.
Create the table of k + 1 rows and n + 1 columns of zeros, mutable, as i32.
Loop over t from 1 to k.
Declare max_diff inside that loop with let mut, starting at i32::MIN. No day has been seen yet, so the running best must lose to any real candidate, and candidates can be negative. Each t starts its own running best.
Loop over i from 1 to n.
Choose the best of three options for dp[t][i]: no sale on day i (dp[t][i - 1]), fewer transactions (dp[t - 1][i]), or selling today the stock bought on the best earlier day (max_diff + prices[i - 1]). Chain two max calls to compare three values.
Update max_diff with today's buy candidate, dp[t - 1][i] - prices[i - 1], keeping the larger value. This comes after computing dp[t][i], since today's candidate is meant for sales on later days.
Return dp[k][n].

The solution in Rust

impl Solution {
    fn max_profit(prices: Vec<i32>, k: i32) -> i32 {
        let n = prices.len();
        let k = k as usize;
        let mut dp = vec![vec![0i32; n + 1]; k + 1];
        for t in 1..=k {
            let mut max_diff = i32::MIN;
            for i in 1..=n {
                dp[t][i] = dp[t][i - 1].max(dp[t - 1][i]).max(max_diff + prices[i - 1]);
                max_diff = max_diff.max(dp[t - 1][i] - prices[i - 1]);
            }
        }
        dp[k][n]
    }
}

The Rust details worth knowing:

Chained method calls. a.max(b).max(c) is the maximum of three values: the first call yields an i32, and the second compares it with c.
i32::MIN as a starting value. It is the smallest i32, -2147483648, so any real candidate replaces it. It is risky to add to, though: max_diff + prices[i - 1] on day 1 evaluates i32::MIN + price. With a price of 0 or more the sum only moves up, so nothing wraps. A negative price would push it below the minimum, and in an optimized build that wraps silently into a huge positive number.
Variable scope. max_diff is declared inside the t loop, so it exists only for the current row and starts fresh for the next one.
Mutation with mut. Both dp and max_diff change after creation, so both need mut. Without it the compiler rejects the assignments.
Tail expression. dp[k][n] has no semicolon and no return, so it is the function's value.

Complexity

Time: O(k * n). The two loops visit each cell once, and each cell now costs a few comparisons instead of a scan over earlier days.

Space: O(k * n). The table is unchanged. Because row t only reads rows t and t - 1, two rows would be enough if you wanted O(n) space.

Edge cases and common mistakes

Prices that only fall. [5, 4, 3] with k = 2 gives 0, because the no-sale options keep every cell at 0.
No prices or k = 0. An empty vector has n = 0, so the inner loop never runs and the result is 0. With k = 0 the outer loop never runs and the result is 0 as well.
Starting max_diff at 0. That pretends a free purchase happened before day 1 and can report a profit that doesn't exist.
Large k. The table has k + 1 rows, so an enormous k allocates a lot of memory even though no more than n / 2 transactions can be useful.

Testing

prices = [2, 4, 1], k = 2 gives 2.
prices = [3, 2, 6, 5, 0, 3], k = 2 gives 7.
prices = [7, 1, 5, 3, 6, 4], k = 1 gives 5.
prices = [1, 5, 2, 8, 3, 9], k = 3 gives 16.
prices = [], k = 2 gives 0.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free