Visit array positions to maximize score

Array Dynamic Programming

37.5% acceptance

Feb 25, 2026

533

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(nums: Vec<i32>, x: i32) -> i64 {
    const NEG_INF: i64 = i64::MIN / 2;
    let x = x as i64;
    let mut dp = [NEG_INF; 2];
    dp[(nums[0] % 2) as usize] = nums[0] as i64;
    for i in 1..nums.len() {
      let p = (nums[i] % 2) as usize;
      let q = 1 - p;
      let gain = nums[i] as i64;
      let via_same = if dp[p] != NEG_INF { dp[p] + gain } else { NEG_INF };
      let via_diff = if dp[q] != NEG_INF { dp[q] - x + gain } else { NEG_INF };
      dp[p] = dp[p].max(via_same.max(via_diff));
    }
    dp[0].max(dp[1])
  }
}