dp_caching_3.go

const (
    INF = int(1e9)
)

var (
    cache [100001][2]int
    nums [100001]int
    N int
)

func maxProfit(prices []int) int {
    init_all(prices)
    return run(0, 0)
}

func init_all(prices []int) {
    N = len(prices)
    for i := range prices {
        cache[i][0] = -1
        cache[i][1] = -1
        nums[i] = prices[i]
    }
}

func run(idx int, taken int) int {
    if idx == N && taken == 1 {
        return -INF
    }
    if idx == N && taken == 0 {
        return 0
    }
    if cache[idx][taken] != -1 {
        return cache[idx][taken]
    }
    if taken == 1 {
        cache[idx][taken] = max(
            run(idx + 1, 1),
            nums[idx],
        )
        return cache[idx][taken]
    }
    cache[idx][taken] = max(
        run(idx + 1, 0),
        -nums[idx] + run(idx + 1, 1),
    )
    return cache[idx][taken]
}