dp_caching_1.py

class Solution:
    def maxProfit(self, nums: List[int]) -> int:
        return sol8(nums)

def sol1(nums):
    N = len(nums)
    INF = 10**10

    @cache
    def run(idx, taken):
        if idx == N and taken: return -INF
        if idx == N: return 0
        if taken: return max(run(idx + 1, 1), nums[idx])
        return max(run(idx + 1, 0), -nums[idx] + run(idx + 1, 1))

    return run(0, 0)