Start learning free

LESSON 325 OF 348 · DYNAMIC PROGRAMMING

Best Time to Buy and Sell Stock in Kotlin: DP for At Most K Trades

Practice O(n3) 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 9
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Best Time To Buy Stock in Kotlin, explained

    Problem overview

    The function maxProfit(prices, k) receives an IntArray where prices[i] is the price of a stock on one day, and an integer k. It returns the largest total profit from at most k transactions, where a transaction is one buy followed by one sell. You can't hold two shares at once: a sale must happen before the next purchase.

    With prices = [2, 4, 1] and k = 2, the answer is 2: buy at 2 and sell at 4. With 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: best profit for each number of trades and days

    Trying every set of buy and sell days grows exponentially. Dynamic programming fixes that by remembering answers to smaller questions. Let dp[t][i] be the best profit using at most t transactions in the first i days. Row 0 (no trades) and column 0 (no days) are both 0, and the table starts out that way.

    To fill dp[t][i], consider the last day, day i:

    • No sale on day i. Then the answer is no better than what the first i - 1 days gave, dp[t][i - 1]. Using one transaction fewer, dp[t - 1][i], is also a candidate, since "at most" means spare transactions can go unused.
    • A sale on day i. The stock was bought on some earlier day j. That transaction earns prices[i - 1] - prices[j - 1], and before day j there were at most t - 1 transactions, worth dp[t - 1][j - 1].

    The table entry is the best of all these options. The answer is dp[k][n], where n is the number of days. Trying every buy day j for every cell is a third nested loop. A running maximum can replace that loop, as the faster version of this problem shows; here it stays because it shows the idea most directly.

    Step by step

    1. Store prices.size in n. It is used repeatedly, for the table and the loops.
    2. Create dp with k + 1 rows and n + 1 columns, all zeros. The extra row and column are the "no trades" and "no days" cases.
    3. Loop t from 1 to k. Row 0 stays at zero.
    4. Loop i from 1 to n. Column 0 stays at zero. Day numbers start at 1 in the table, but prices is indexed from 0, so day i has price prices[i - 1].
    5. Start from the no-sale options. Set dp[t][i] to the larger of dp[t][i - 1] and dp[t - 1][i].
    6. Try every buy day j before day i, from 1 up to i - 1. Buying must come before selling.
    7. Compute the profit of buying on day j and selling on day i.
    8. Keep the better value. Compare dp[t - 1][j - 1] + profit with the current dp[t][i]. The first part is the best result for the days before the purchase, with one fewer transaction.
    9. 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) {
            for (i in 1..n) {
                dp[t][i] = maxOf(dp[t][i - 1], dp[t - 1][i])
                for (j in 1 until i) {
                    val profit = prices[i - 1] - prices[j - 1]
                    dp[t][i] = maxOf(dp[t][i], dp[t - 1][j - 1] + profit)
                }
            }
        }
        return dp[k][n]
    }
}

    The Kotlin details worth a closer look:

    • The table. Array(k + 1) { IntArray(n + 1) } calls the lambda once per row, so each row is a separate IntArray of zeros. Writing dp[t][i] = ... changes one cell of one row.
    • Ranges. 1..k and 1..n include the upper end, which is the last transaction count and the last day. 1 until i excludes i, so the buy day is always strictly earlier than the sell day.
    • maxOf. It returns the larger of two values, and a call with two Int arguments gives an Int.
    • Assigning inside the inner loop. dp[t][i] is updated repeatedly, once for each j. It always keeps the best value seen so far, so the final value is the maximum over all options.

    Complexity

    Time: O(k * n²). There are k * n cells, and each one runs a loop over up to n buy days. A running maximum, described above, brings it down to O(k * n).

    Space: O(k * n). The table has (k + 1) * (n + 1) cells. A very large k makes the table large even when n is tiny, because the code allocates all k + 1 rows.

    Edge cases and common mistakes

    • Falling prices. For [5, 4, 3, 1] with k = 3 the result is 0, because no transaction earns anything and trades can stay unused.
    • k = 0. The loop over t never runs, and dp[0][n] is 0.
    • Empty prices. With no days, dp[k][0] is 0 and the function returns 0.
    • More transactions than useful. For [3, 2, 6, 5, 0, 3] with k = 5 the answer is still 7, the same as with k = 2. Spare transactions simply go unused.
    • Off-by-one in prices. Using prices[i] instead of prices[i - 1] reads one day too far and throws ArrayIndexOutOfBoundsException on the last day.
    • Letting j reach i. That would model a buy and sell on the same day, which earns 0. It is harmless here, but the spec says to buy first.
    • Using dp[t - 1][j] for the part before the purchase. Day j is the buy day, so the earlier transactions must fit in days 1 to j - 1.

    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