2786. Visit Array Positions to Maximize Score

Description

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.
For each position i that you visit, you get a score of nums[i].
If you move from a position i to a position j and the parities of nums[i] and nums[j] differ, then you lose a score of x.

Return the maximum total score you can get.

Note that initially you have nums[0] points.

Example 1:

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.
The corresponding values are 2, 6, 1 and 9. Since the integers 6 and 1 have different parities, the move 2 -> 3 will make you lose a score of x = 5.
The total score will be: 2 + 6 + 1 + 9 - 5 = 13.

Example 2:

Input: nums = [2,4,6,8], x = 3
Output: 20
Explanation: All the integers in the array have the same parities, so we can visit all of them without losing any score.
The total score is: 2 + 4 + 6 + 8 = 20.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i], x <= 10⁶

Solutions

Solution 1: Dynamic Programming

Based on the problem description, we can draw the following conclusions:

Moving from position \(i\) to position \(j\), if \(nums[i]\) and \(nums[j]\) have different parities, then \(x\) points will be lost;
Moving from position \(i\) to position \(j\), if \(nums[i]\) and \(nums[j]\) have the same parity, then no points will be lost.

Therefore, we can use an array \(f\) of length \(2\) to represent the maximum score when the current position's parity is \(0\) and \(1\). Initially, the values of \(f\) are \(-\infty\), and then we initialize \(f[nums[0] \& 1] = nums[0]\), indicating the score at the initial position.

Next, we start traversing the array \(nums\) from position \(1\). For each position \(i\) corresponding to the value \(v\), we update the value of \(f[v \& 1]\) to be the larger value between \(f[v \& 1]\) and \(f[v \& 1 \oplus 1] - x\) plus \(v\), i.e., \(f[v \& 1] = \max(f[v \& 1], f[v \& 1 \oplus 1] - x) + v\).

The answer is the larger value between \(f[0]\) and \(f[1]\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(nums\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

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)

class Solution {
    public long maxScore(int[] nums, int x) {
        long[] f = new long[2];
        Arrays.fill(f, -(1L << 60));
        f[nums[0] & 1] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int v = nums[i];
            f[v & 1] = Math.max(f[v & 1], f[v & 1 ^ 1] - x) + v;
        }
        return Math.max(f[0], f[1]);
    }
}

class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        const long long inf = 1LL << 60;
        vector<long long> f(2, -inf);
        f[nums[0] & 1] = nums[0];
        int n = nums.size();
        for (int i = 1; i < n; ++i) {
            int v = nums[i];
            f[v & 1] = max(f[v & 1], f[v & 1 ^ 1] - x) + v;
        }
        return max(f[0], f[1]);
    }
};

func maxScore(nums []int, x int) int64 {
    const inf int = 1 << 40
    f := [2]int{-inf, -inf}
    f[nums[0]&1] = nums[0]
    for _, v := range nums[1:] {
        f[v&1] = max(f[v&1], f[v&1^1]-x) + v
    }
    return int64(max(f[0], f[1]))
}

function maxScore(nums: number[], x: number): number {
    const f: number[] = Array(2).fill(-Infinity);
    f[nums[0] & 1] = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        const v = nums[i];
        f[v & 1] = Math.max(f[v & 1], f[(v & 1) ^ 1] - x) + v;
    }
    return Math.max(...f);
}

2786. Visit Array Positions to Maximize Score

Description

Solutions

Solution 1: Dynamic Programming

Comments