leetcode 188

best_time_to_buy_and_sell_stock_IV.kt

class Solution {
    fun maxProfit(k: Int, prices: IntArray): Int {
        return if(prices.isEmpty()) {
            0
        } else {
            // dp[i][j]: max profit from at most i transactions using prices[0..j]
            val dp = Array(k+1) { IntArray(prices.size) {0}}
            
            var currProfit: Int // local max profit
            for(i in 1..k) {
                currProfit = -prices[0] // you need to buy before selling
                
                for(j in 1..prices.lastIndex) {
                    // max(do nothing, sell today), sell won't increase transaction count
                    dp[i][j] = Math.max(dp[i][j-1], currProfit + prices[j]) 
                    
                    // max(currProfit, buy today), this value is used for the next loop
                    // we need to buy before selling, so we check here should we buy today
                    // we need to use dp[i-1][j-1] because buy a stock increase the transaction count
                    currProfit = Math.max(currProfit, dp[i-1][j-1] - prices[j]) 
                }
            }
            
            dp[k][prices.lastIndex]
        }
    }
}