Skip to main content

20240614 2786 - Medium - DP

2786. Visit Array Positions to Maximize Score​

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        @cache
        def dp(i, j):
            if i == len(nums):
                return 0
            if nums[i] % 2 != j:
                return dp(i+1, j)
            return max(dp(i+1, j), dp(i+1, j^1) - x) + nums[i]
        return dp(0, nums[0]%2)