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 positionj
such thati < j
. - For each position
i
that you visit, you get a score ofnums[i]
. - If you move from a position
i
to a positionj
and the parities ofnums[i]
andnums[j]
differ, then you lose a score ofx
.
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:
- 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)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|