Skip to content

2786. Visit Array Positions to Maximize Score 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  long long maxScore(vector<int>& nums, int x) {
    // Note that we always need to take nums[0], so the initial definition might
    // not hold true.

    // dp0 := the maximum score so far with `nums` ending in an even number
    long dp0 = nums[0] - (nums[0] % 2 == 1 ? x : 0);
    // dp1 := the maximum score so far with `nums` ending in an odd number
    long dp1 = nums[0] - (nums[0] % 2 == 0 ? x : 0);

    for (int i = 1; i < nums.size(); ++i)
      if (nums[i] % 2 == 0)
        dp0 = nums[i] + max(dp0, dp1 - x);
      else
        dp1 = nums[i] + max(dp1, dp0 - x);

    return max(dp0, dp1);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public long maxScore(int[] nums, int x) {
    // Note that we always need to take nums[0], so the initial definition might
    // not hold true.

    // dp0 := the maximum score so far with `nums` ending in an even number
    long dp0 = nums[0] - (nums[0] % 2 == 1 ? x : 0);
    // dp1 := the maximum score so far with `nums` ending in an odd number
    long dp1 = nums[0] - (nums[0] % 2 == 0 ? x : 0);

    for (int i = 1; i < nums.length; ++i)
      if (nums[i] % 2 == 0)
        dp0 = nums[i] + Math.max(dp0, dp1 - x);
      else
        dp1 = nums[i] + Math.max(dp1, dp0 - x);

    return Math.max(dp0, dp1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def maxScore(self, nums: list[int], x: int) -> int:
    # Note that we always need to take nums[0], so the initial definition might
    # not hold true.

    # dp0 := the maximum score so far with `nums` ending in an even number
    dp0 = nums[0] - (x if nums[0] % 2 == 1 else 0)
    # dp0 := the maximum score so far with `nums` ending in an odd number
    dp1 = nums[0] - (x if nums[0] % 2 == 0 else 0)

    for i in range(1, len(nums)):
      if nums[i] % 2 == 0:
        dp0 = nums[i] + max(dp0, dp1 - x)
      else:
        dp1 = nums[i] + max(dp1, dp0 - x)

    return max(dp0, dp1)