# Visit Array Positions to Maximize Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/visit-array-positions-to-maximize-score)
Canonical: https://scaleengineer.com/dsa/problems/visit-array-positions-to-maximize-score
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## 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 _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`

# Approaches
## Brute-force Dynamic Programming
This approach uses a straightforward dynamic programming solution. We define `dp[i]` as the maximum score achievable by ending a path of visited positions at index `i`. To compute `dp[i]`, we consider all possible preceding positions `j` (where `j < i`) that we could have jumped from. The score for jumping from `j` to `i` is the score of the path ending at `j` (`dp[j]`) plus the value `nums[i]`, minus a penalty `x` if the parities of `nums[j]` and `nums[i]` differ. We take the maximum over all possible `j`'s to determine `dp[i]`. The final answer is the maximum score found in the entire `dp` array.
**Time:** O(n^2), where n is the number of elements in `nums`. There are two nested loops: the outer loop runs `n-1` times, and the inner loop runs up to `n-1` times for each outer iteration. · **Space:** O(n), where n is the number of elements in `nums`. This is required for the DP array.
**Pros:** The logic is a direct translation of the problem statement into a DP recurrence, making it relatively easy to understand.; It correctly solves the problem for smaller input sizes.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.; Uses O(n) space, which might be significant for very large `n`.
### Explanation
We create a DP array, `dp`, of the same size as `nums`. `dp[i]` will store the maximum score of a path ending at index `i`.

The base case is `dp[0] = nums[0]`, as the path must start at index 0. We initialize all other `dp` entries to a very small number.

We then iterate from `i = 1` to `n-1`. For each `i`, we need to find the best previous position `j` to jump from. We do this by iterating `j` from `0` to `i-1`. For each `j`, we calculate the potential score if we extend the path ending at `j` by visiting `i`. This score is `dp[j] + nums[i]`. If `nums[j]` and `nums[i]` have different parities, we subtract the penalty `x`.

The value of `dp[i]` is then the maximum of these potential scores over all `j < i`. The recurrence relation can be expressed as:
`dp[i] = max_{0 <= j < i} (dp[j] + nums[i] - ((nums[j] % 2 != nums[i] % 2) ? x : 0))`

After the loops complete, the `dp` array is filled. The maximum score might be achieved by ending at any index, so the final answer is the maximum value in the `dp` array.

```java
class Solution {
    public long maxScore(int[] nums, int x) {
        int n = nums.length;
        long[] dp = new long[n];
        
        dp[0] = nums[0];

        for (int i = 1; i < n; i++) {
            long maxPrevJumpScore = Long.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                long penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
                maxPrevJumpScore = Math.max(maxPrevJumpScore, dp[j] - penalty);
            }
            dp[i] = nums[i] + maxPrevJumpScore;
        }

        long maxTotalScore = Long.MIN_VALUE;
        for (long score : dp) {
            maxTotalScore = Math.max(maxTotalScore, score);
        }
        return maxTotalScore;
    }
}
```
### Algorithm
*   Initialize a `long` array `dp` of size `n`, where `n` is the length of `nums`. `dp[i]` will store the maximum score of a path ending at index `i`.
*   Set the base case: `dp[0] = nums[0]`, as any path must start at index 0.
*   Iterate with a variable `i` from 1 to `n-1`:
    *   For each `i`, iterate with a variable `j` from 0 to `i-1`.
    *   Calculate the score if we jump from a path ending at `j` to the element at `i`.
    *   The score is `dp[j] + nums[i]`. A penalty `x` is subtracted if `nums[i]` and `nums[j]` have different parities.
    *   Update `dp[i]` with the maximum score found among all possible previous positions `j`.
    *   The recurrence relation is: `dp[i] = max(dp[i], dp[j] + nums[i] - penalty)`.
*   After filling the `dp` array, the answer is the maximum value within `dp`, since the path can end at any index.

## Optimized Dynamic Programming
This approach optimizes the dynamic programming solution by reducing the state. We observe that to calculate the maximum score ending at index `i`, we only need to know the maximum score of a path ending with an even number and the maximum score of a path ending with an odd number from the previous steps. We don't need to check every single previous index `j`.

By maintaining just two variables—`evenMaxScore` and `oddMaxScore`—we can compute the new maximums in constant time at each step. This eliminates the inner loop of the brute-force approach, reducing the overall time complexity from quadratic to linear.
**Time:** O(n), where n is the number of elements in `nums`. We perform a single pass through the array. · **Space:** O(1), as we only use a constant number of variables regardless of the input size.
**Pros:** Extremely efficient with O(n) time complexity, which passes the given constraints.; Uses O(1) space, making it highly memory-efficient.
**Cons:** The logic, especially the initialization, is more abstract and might be less intuitive than the brute-force approach.
### Explanation
The key insight is that the cost of jumping to `nums[i]` only depends on the parity of the last element in the path. Therefore, we can optimize the state of our DP. Instead of `dp[i]`, we maintain two variables throughout our iteration:

1.  `evenMaxScore`: The maximum score of any valid path seen so far that ends with an even number.
2.  `oddMaxScore`: The maximum score of any valid path seen so far that ends with an odd number.

We start by initializing these scores based on `nums[0]`. Since the path must start at `nums[0]`, if `nums[0]` is even, `evenMaxScore` is `nums[0]`. To handle future calculations, we can set `oddMaxScore` to `nums[0] - x`, representing the score if we had to switch parity to start with an odd number. A symmetric initialization is done if `nums[0]` is odd.

Then, we iterate from `i = 1` to `n-1`. For each `nums[i]`:
- If `nums[i]` is even, the new `evenMaxScore` is `nums[i]` plus the better of two options: coming from a previous even path (`evenMaxScore`) or coming from a previous odd path with a penalty (`oddMaxScore - x`).
- If `nums[i]` is odd, the logic is similar for updating `oddMaxScore`.

After iterating through all numbers, the final answer is simply the maximum of `evenMaxScore` and `oddMaxScore`.

```java
class Solution {
    public long maxScore(int[] nums, int x) {
        long evenMaxScore;
        long oddMaxScore;

        // Initialize scores based on the first element
        if (nums[0] % 2 == 0) {
            evenMaxScore = nums[0];
            oddMaxScore = nums[0] - x;
        } else {
            oddMaxScore = nums[0];
            evenMaxScore = nums[0] - x;
        }

        for (int i = 1; i < nums.length; i++) {
            int currentNum = nums[i];
            if (currentNum % 2 == 0) { // Current number is even
                evenMaxScore = Math.max(evenMaxScore + currentNum, oddMaxScore - x + currentNum);
            } else { // Current number is odd
                oddMaxScore = Math.max(oddMaxScore + currentNum, evenMaxScore - x + currentNum);
            }
        }

        return Math.max(evenMaxScore, oddMaxScore);
    }
}
```
### Algorithm
*   Initialize two `long` variables: `evenMaxScore` to track the max score ending in an even number, and `oddMaxScore` for an odd number.
*   Handle the first element `nums[0]`. If `nums[0]` is even, initialize `evenMaxScore = nums[0]` and `oddMaxScore = nums[0] - x`. If `nums[0]` is odd, initialize `oddMaxScore = nums[0]` and `evenMaxScore = nums[0] - x`. This setup correctly accounts for the penalty of a hypothetical first move with a parity switch.
*   Iterate through the array from `i = 1` to `n-1`.
*   At each element `nums[i]`:
    *   If `nums[i]` is even, calculate the new `evenMaxScore`. It's the maximum of jumping from a previous even-ending path (`evenMaxScore + nums[i]`) or an odd-ending path (`oddMaxScore + nums[i] - x`).
    *   If `nums[i]` is odd, calculate the new `oddMaxScore` similarly. It's the maximum of jumping from an odd-ending path (`oddMaxScore + nums[i]`) or an even-ending path (`evenMaxScore + nums[i] - x`).
*   After the loop, the maximum possible score is `max(evenMaxScore, oddMaxScore)`.

# Solutions
### Java

```java
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]);
  }
}

```

### CPP

```cpp
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]);
  }
};

```

### Python

```python
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)

```