Leetcode # 2786. Visit Array Positions to Maximize Score

https://leetcode.com/contest/biweekly-contest-109/problems/visit-array-positions-to-maximize-score/

Solution

Time Complexity: O(len(nums))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxScore(self, nums: List[int], x: int) -> int:
    last_dp = [-inf, -inf]
    last_dp[nums[0] % 2] = nums[0]
    for i in range(1, len(nums)):
      is_odd = nums[i] % 2 == 1
      from_even = last_dp[0] + nums[i] - (x if is_odd else 0) 
      from_odd  = last_dp[1] + nums[i] - (0 if is_odd else x) 
      last_dp[1 if is_odd else 0] = max(from_even, from_odd)
    return max(last_dp)

Last Updated on 2023/08/16 by A1go