[Leetcode] 188. Best Time to Buy and Sell Stock IV

예전에 풀었던 주식 판매 문제. 최대 k 번의 매매를 할 수 있으므로 prices 를 순회하며 이전값과 비교해 현재의 최선값을 구하는, 전형적인 동적 프로그래밍 문제이다.

먼저 매수의 경우 현재 매수가와 이전 판매에서의 얻은 이득 - 매수비용을 비교한다. 이후 매도의 경우 현재 판매해서 얻은 비용과 이전에 매수한 주식을 팔아서 얻는 이득 을 비교해가며 진행하면 된다.

안쪽 for 문 안에서 최댓값을 비교할 때 현재의 i 를 사용하는데, 바깥 for 문 에서 가격이 계속 새로 들어오므로 '왜 현재가를 비교하지?' 가 아니라 "지금 가격으로 매수 또는 매도를 진행하는 비용" 과 "이전의 가격으로 매수 또는 매도를 진행했을 때의 비용" 을 비교하는 것이라 생각하면 된다.

function maxProfit(k: number, prices: number[]): number {
    let buy = Array.from({ length: k + 1 }, () => -1000000000)
    let sell = Array.from({ length: k + 1 }, () => 0)

    for (const p of prices) {
        let nextBuy = [...buy]
        let nextSell = [...sell]

        for (let i = 1; i <= k; i++) {
            nextBuy[i] = Math.max(buy[i], sell[i - 1] - p)
            nextSell[i] = Math.max(sell[i], buy[i] + p)
        }

        buy = nextBuy
        sell = nextSell
    }
    
    return sell[k]
};