2786-访问数组中的位置使分数最大

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

• 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
• 对于你访问的位置 i ，你可以获得分数 nums[i] 。
• 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ，你一开始的分数为 nums[0] 。

示例 1：

**输入：** nums = [2,3,6,1,9,2], x = 5
**输出：** 13
**解释：** 我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。

示例 2：

**输入：** nums = [2,4,6,8], x = 3
**输出：** 20
**解释：** 数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。

提示：

• 2 <= nums.length <= 105
• 1 <= nums[i], x <= 106

解题思路

本题很容易想到用动态规划求解
设res[i]为跳到位置i时的最大分数，则有递推关系式：
res[i]=max{nums奇偶性相同时res的最大值+nums[i],nums奇偶性不同时res的最大值+nums[i]-x}
我们用max0表示nums为偶数对应的res的最大值，max1表示nums为奇数时对应的res的最大值
最后返回的结果就是nums为偶数或奇数时最大的res。

代码

class Solution {
    public long maxScore(int[] nums, int x) {
        long max0 = Integer.MIN_VALUE;//nums偶数res最大值，设为Integer.MIN_VALUE更好，不要设为0
        long max1 = Integer.MIN_VALUE;//nums奇数res最大值，设为Integer.MIN_VALUE更好，不要设为0
        long[] res = new long[nums.length];//保存跳到每个位置时能够获得的最大分数
        res[0]=nums[0];//在位置0获得分数nums[0]
        if(nums[0]%2==0){//位置i为偶数
            max0=res[0];
        }else {//位置i为奇数
            max1=res[0];
        }
        for (int i = 1; i < nums.length; i++) {
            long a;//偶数
            long b;//奇数
            if(nums[i]%2==0){
                a=max0+nums[i];//从偶数跳过来
                b=max1+nums[i]-x;//从奇数跳过来
                res[i]=Math.max(a,b);
                max0=Math.max(res[i],max0);
            }else {
                a=max0+nums[i]-x;//从偶数跳过来
                b=max1+nums[i];//从奇数跳过来
                res[i]=Math.max(a,b);
                max1=Math.max(res[i],max1);
            }
        }
        return Math.max(max0,max1);
    }
}