发表于 2024.06.14

• 此类单向转移+寻找分数最大化的问题可以考虑使用动态规划做法。最朴素的dp是定义dp[i]为转移到第i个元素的最大分数，其中dp[i] = max(dp[j] + nums[i] - (x if nums[i] % 2 != nums[j] % 2 else 0))，j < i，这样需要双重循环，需要考虑优化：仅使用两个变量odd_max和even_max表示已遍历的数组元素中，转移到奇数和偶数的最大分数，这样可以将遍历压到一重。其中遍历到偶数元素时，更新even_max = max(even_max + nums[i], odd_max + nums[i] - x)，遍历到奇数元素时，更新odd_max = max(odd_max + nums[i], even_max + nums[i] - x)。最后返回max(odd_max, even_max)即可。

  使用第二个dp状态转移的过程中，如果当前元素为奇数，其中最优解要么就从前一个偶数转移过来，要么就从前一个奇数转移过来。此外，偶数的最优解even_max必定指向前一个偶数，奇数同理。可以简单证明一下，如果even_max并不指向前一个偶数a，而是指向更前面的偶数b，那么从b转移到a所得的分数必定大于even_max(偶数跳偶数没有损失)，奇数同理。因此，上述做法满足最优子结构性质(原问题的最优解包含子问题的最优解)。此外，由于转移过程是单向的，一旦跳到某个元素后，就不会再跳回来，因此满足无后效性。第二个dp得证。

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

  参考资料：

  • 动态规划的特性
• LC 题目链接