Welcome to Subscribe On Youtube
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
-
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) { f[nums[i] & 1] = Math.max(f[nums[i] & 1] + nums[i], f[nums[i] & 1 ^ 1] + nums[i] - x); } 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) { f[nums[i] & 1] = max(f[nums[i] & 1] + nums[i], f[nums[i] & 1 ^ 1] + nums[i] - x); } return max(f[0], f[1]); } };
-
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] + v, f[v & 1 ^ 1] + v - x) return max(f)
-
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]+v, f[v&1^1]+v-x) } return int64(max(f[0], f[1])) } func max(a, b int) int { if a > b { return a } return b }
-
function maxScore(nums: number[], x: number): number { const inf = 1 << 30; const f: number[] = Array(2).fill(-inf); f[nums[0] & 1] = nums[0]; for (let i = 1; i < nums.length; ++i) { f[nums[i] & 1] = Math.max(f[nums[i] & 1] + nums[i], f[(nums[i] & 1) ^ 1] + nums[i] - x); } return Math.max(f[0], f[1]); }