LeetCode 2786. Visit Array Positions to Maximize Score Solution in Java, C++, Python & More | Explanation + Code

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 <= 105
• 1 <= nums[i], x <= 106

Solutions

Solution 1: Dynamic Programming

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

1. Moving from position i to position j, if nums[i] and nums[j] have different parities, then x points will be lost;
2. 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 -∞, 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).

PythonJavaC++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)(code-box)

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]); } }(code-box)

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]); } };(code-box)

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])) }(code-box)

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); }(code-box)