Visit Array Positions to Maximize Score — LeetCode 2786 Python Solution

The problem

You are given a 0-indexed integer array nums and a positive integer x. You are initially at position 0 in the array and you can visit other positions according to the following rules: If you are currently in position i, then you can move to any position j such that i < j.

Example

Input

nums = [2,3,6,1,9,2], x = 5

Output

13

Explanation

We can visit the following positions in the array: 0 -> 2 -> 3 -> 4.

Python solution

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        f = [-inf] * 2
        f[nums[0] & 1] = nums[0]
        for v in nums[1:]:
            f[v & 1] = max(f[v & 1], f[v & 1 ^ 1] - x) + v
        return max(f)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2786. Visit Array Positions to Maximize Score is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems