2786. Visit Array Positions to Maximize Score

link

It's dp but can't resolve in contest.

Made a backtrack first. The backtrack is a little different from common solution.

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        
        n = len(nums)
        
        o = []
        e = []
        for i in range(n):
            if nums[i] % 2 == 0:
                e.append(i)
            else:
                o.append(i)

        @cache
        def backtrack(s):
            if s == n - 1:
                return nums[s]
            
            res = nums[s]
            find1, find2 = None, None
            
            if nums[s] % 2 == 0:
                idx1 = bisect.bisect_left(e, s) + 1
                if idx1 != len(e):
                    find1 = e[idx1]
                idx2 = bisect.bisect_left(o, s)
                if idx2 != len(o):
                    find2 = o[idx2]
            else:
                idx1 = bisect.bisect_left(o, s) + 1
                if idx1 != len(o):
                    find1 = o[idx1]
                idx2 = bisect.bisect_left(e, s)
                if idx2 != len(e):
                    find2 = e[idx2]

            if find1 != None:
                res = max(res, nums[s] + backtrack(find1))
            if find2 != None:
                res = max(res, nums[s] - x + backtrack(find2))

            return res
                    
        return backtrack(0)

Giving rights thought(pick or not pick)

dp[i][0] the maximum total score you can get at i position if i % 2 == 0 dp[i][1] the maximum total score you can get at i position if i % 2 == 1

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        
        n = len(nums)

        if n == 1:
            return nums[0]
        
        # default value is important here
        # you need to make first iteration(i == 1) reasonable
        dp = [[float('-inf')] * 2 for i in range(n)]

        if nums[0] % 2 == 0:
            dp[0][0] = nums[0]
        else:
            dp[0][1] = nums[0]
        

        for i in range(1, n):

            # if we choose not pick this one, the state come from previous iteration
            dp[i][0] = dp[i-1][0]
            dp[i][1] = dp[i-1][1]

            if nums[i] % 2 == 0:
                dp[i][0] = max(dp[i-1][0] + nums[i], dp[i-1][1] + nums[i] - x)
            else:
                dp[i][1] = max(dp[i-1][1] + nums[i], dp[i-1][0] + nums[i] - x)

        return max(dp[-1])