Start learning free

LESSON 326 OF 348 · DYNAMIC PROGRAMMING

Best Time to Buy and Sell Stock in Kotlin: O(k * n) DP with maxDiff

Practice O(n2) Read the full explanation

Say you have an array 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 (ie, you must sell the stock before you buy again).

Example 1:

Input: [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: [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
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Best Time To Buy Stock in Kotlin, explained

    Problem overview

    The function maxProfit(prices, k) takes an IntArray of daily stock prices and an integer k, and returns the largest profit from at most k transactions. A transaction is a buy followed by a sell, and you must sell before you buy again.

    For prices = [2, 4, 1] and k = 2 the answer is 2 (buy at 2, sell at 4). 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.

    Approach: replace the buy-day loop with a running best

    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. When the last transaction sells on day i after buying on day j, the total is

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

    The slow version tries every j for every cell, which costs O(k * n²) in total. But look at the formula: the part that depends on j is dp[t - 1][j - 1] - prices[j - 1], and the sale price prices[i - 1] doesn't depend on j at all. For a fixed t, the best buy day for any sale day is therefore the one that maximises that j-part among the days so far. Instead of recomputing the maximum for each i, keep it in a variable and update it as the days go by. That variable is maxDiff, and with it each cell costs O(1).

    This lesson's code updates maxDiff with dp[t - 1][i] - prices[i - 1] rather than dp[t - 1][i - 1]. This is still correct. The only difference is that it also considers buying on day i with the profit of day i already in hand, and a sale on that same day would earn nothing, so it can never beat an honest candidate.

    Step by step

    1. Store prices.size in n and create dp with k + 1 rows and n + 1 columns, filled with zeros.
    2. Loop t from 1 to k. Row 0 stays at zero.
    3. Declare maxDiff as a var inside that loop, so it restarts for every t. It holds the best value of dp[t - 1][j] - prices[j - 1] over the days seen so far. Its starting value is Int.MIN_VALUE: no day has been seen, and any real candidate should beat it.
    4. Loop i from 1 to n.
    5. Set dp[t][i] to the best of three values: no sale today (dp[t][i - 1]), one transaction fewer (dp[t - 1][i]), and selling today the stock bought on the best earlier day (maxDiff + prices[i - 1]).
    6. Update maxDiff afterwards with today's candidate dp[t - 1][i] - prices[i - 1]. The update comes after the cell is computed, so a stock bought today is only available for sale on later days.
    7. Return dp[k][n].

    The solution in Kotlin

    class Solution {
    fun maxProfit(prices: IntArray, k: Int): Int {
        val n = prices.size
        val dp = Array(k + 1) { IntArray(n + 1) }
        for (t in 1..k) {
            var maxDiff = Int.MIN_VALUE
            for (i in 1..n) {
                dp[t][i] = maxOf(maxOf(dp[t][i - 1], dp[t - 1][i]), maxDiff + prices[i - 1])
                maxDiff = maxOf(maxDiff, dp[t - 1][i] - prices[i - 1])
            }
        }
        return dp[k][n]
    }
}

    The Kotlin details worth a closer look:

    • var versus val. maxDiff changes on every pass, so it must be a var. n and dp never get a new value, so they are val. The cells of dp can still be assigned.
    • Int.MIN_VALUE as a sentinel. It is -2147483648, the smallest Int. On day 1 the code computes Int.MIN_VALUE + prices[0]. For a non-negative price that moves the value up, so nothing overflows. A negative price would wrap around to a huge positive number, which prices never are.
    • Nested maxOf. maxOf in this form takes two values. For three, nest two calls. (The standard library also has a three-argument overload.)
    • Array of arrays. Array(k + 1) { IntArray(n + 1) } builds the rows with a lambda, so each row is its own array.

    Complexity

    Time: O(k * n). The two loops visit each of the k * n cells once, and every visit does a constant number of comparisons. That is a full factor of n faster than trying every buy day.

    Space: O(k * n). The table has (k + 1) * (n + 1) cells. Row t only reads row t - 1 and itself, so two rows would be enough if memory mattered. A huge k still means a huge table, because every row is allocated up front.

    Edge cases and common mistakes

    • Falling prices. [5, 4, 3, 1] with k = 3 returns 0, since the "one transaction fewer" and "no sale" options keep the zero.
    • k = 0 or no days. maxProfit(intArrayOf(3, 2, 6, 5, 0, 3), 0) and maxProfit(intArrayOf(), 2) both return 0.
    • Surplus transactions. With k = 5, [3, 2, 6, 5, 0, 3] still gives 7, the same as with 2.
    • Declaring maxDiff outside the t loop. The value left over from the previous t already covers every day, including buy days that come after the day being computed, so sales could be paired with purchases from the future.
    • Updating maxDiff before computing the cell. The candidate for day i would then be usable on day i itself. Here the extra candidate happens to be harmless, but keeping the order is the safe habit.
    • Starting maxDiff at 0. That pretends a free purchase happened before the first day and can report profit that doesn't exist.

    Testing

    • prices = [2, 4, 1], k = 2 gives 2.
    • prices = [3, 2, 6, 5, 0, 3], k = 2 gives 7.
    • prices = [3, 2, 6, 5, 0, 3], k = 1 gives 4.
    • prices = [5, 4, 3, 1], k = 3 gives 0.
    • prices = [], k = 2 gives 0.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free