dp_caching_2.go

const (
    INF = int(1e9)
)

var (
    cache [100001][2]int
)

func maxProfit(nums []int) int {
    initCache(len(nums), -1)
    return run(nums, 0, 0)
}

func initCache(N int, val int) {
    for i := range N {
        cache[i][0] = val
        cache[i][1] = val
    }
}

func run(nums []int, idx int, taken int) int {
    N := len(nums)
    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(nums, idx + 1, 1),
            nums[idx],
        )
        return cache[idx][taken]
    }
    cache[idx][taken] = max(
        run(nums, idx + 1, 0),
        -nums[idx] + run(nums, idx + 1, 1),
    )
    return cache[idx][taken]
}