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.
  • 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 themaximum total score you can get.

Note that initially you have nums[0] points.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4

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^5
  • 1 <= nums[i], x <= 10^6

Solution

Method 1 – Dynamic Programming (Track Best for Each Parity)

Intuition

At each position, the best score depends on the parity of the last number you visited. Track the best score so far if the last number is even or odd. For each position, update the best score for its parity, considering a penalty if you switch parity.

Approach

Let best_even be the best score ending at an even number, and best_odd for odd. Initialize with the first number. For each next number, update the best for its parity by considering both staying with the same parity and switching (with penalty).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        long long even = LLONG_MIN, odd = LLONG_MIN;
        if (nums[0] % 2 == 0) even = nums[0];
        else odd = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            int num = nums[i];
            if (num % 2 == 0)
                even = max(even + num, odd + num - x);
            else
                odd = max(odd + num, even + num - x);
        }
        return max(even, odd);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import "math"
func maxScore(nums []int, x int) int64 {
    even, odd := int64(math.MinInt64), int64(math.MinInt64)
    if nums[0]%2 == 0 {
        even = int64(nums[0])
    } else {
        odd = int64(nums[0])
    }
    for i := 1; i < len(nums); i++ {
        num := int64(nums[i])
        if nums[i]%2 == 0 {
            even = max64(even+num, odd+num-int64(x))
        } else {
            odd = max64(odd+num, even+num-int64(x))
        }
    }
    if even > odd {
        return even
    }
    return odd
}
func max64(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public long maxScore(int[] nums, int x) {
        long even = Long.MIN_VALUE, odd = Long.MIN_VALUE;
        if (nums[0] % 2 == 0) even = nums[0];
        else odd = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num % 2 == 0)
                even = Math.max(even + num, odd + num - x);
            else
                odd = Math.max(odd + num, even + num - x);
        }
        return Math.max(even, odd);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maxScore(nums: IntArray, x: Int): Long {
        var even = Long.MIN_VALUE
        var odd = Long.MIN_VALUE
        if (nums[0] % 2 == 0) even = nums[0].toLong() else odd = nums[0].toLong()
        for (i in 1 until nums.size) {
            val num = nums[i].toLong()
            if (nums[i] % 2 == 0)
                even = maxOf(even + num, odd + num - x)
            else
                odd = maxOf(odd + num, even + num - x)
        }
        return maxOf(even, odd)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import List
class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        even = float('-inf')
        odd = float('-inf')
        if nums[0] % 2 == 0:
            even = nums[0]
        else:
            odd = nums[0]
        for num in nums[1:]:
            if num % 2 == 0:
                even = max(even + num, odd + num - x)
            else:
                odd = max(odd + num, even + num - x)
        return max(even, odd)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

pub fn max_score(nums: Vec<i64>, x: i64) -> i64 {
    let mut even = i64::MIN;
    let mut odd = i64::MIN;
    if nums[0] % 2 == 0 {
        even = nums[0];
    } else {
        odd = nums[0];
    }
    for &num in &nums[1..] {
        if num % 2 == 0 {
            even = even.max(odd + num - x).max(even + num);
        } else {
            odd = odd.max(even + num - x).max(odd + num);
        }
    }
    even.max(odd)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function maxScore(nums: number[], x: number): number {
    let even = Number.MIN_SAFE_INTEGER, odd = Number.MIN_SAFE_INTEGER;
    if (nums[0] % 2 === 0) even = nums[0];
    else odd = nums[0];
    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        if (num % 2 === 0)
            even = Math.max(even + num, odd + num - x);
        else
            odd = Math.max(odd + num, even + num - x);
    }
    return Math.max(even, odd);
}

Complexity

  • ⏰ Time complexity: O(n) — One pass through the array.
  • 🧺 Space complexity: O(1) — Only a few variables are used.