给你一个下标从 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
题目大意：第1个数必选，再从数组中选任意数，计算最大的最终分（总分-奇偶相邻的对数*x）。
分析：
（1）由于不同奇偶性质的数相邻时和相同奇偶性质的数相邻时计算得分方式不同。因此考虑选择新的数字nums[i]时应分为两种情况：①在末尾数字是奇数的所有组合中得分最大的组合后面加入nums[i]；在末尾数字是偶数的所有组合中得分最大的组合后面加入nums[i]；
（2）由（1）可知，需要在遍历数组过程中维护末尾数字是奇数的所有组合中得分最大的组合odd的总分pre1，以及末尾数字是偶数的所有组合中得分最大的组合even的总分pre2；
（3）分别考虑nums[i]为奇数和偶数的两种情况。
①nums[i]为奇数时：在odd末尾加入nums[i]的新得分为pre1+nums[i]；在even末尾加入nums[i]的新得分为pre2+nums[i]-x。由于nums[i]是奇数，因此需维护pre1的值，pre1=max(pre1+nums[i],pre2+nums[i]-x)。则此时ans=max(ans,pre1)。
②nums[i]为偶数时：在odd末尾加入nums[i]的新得分为pre1+nums[i]-x；在even末尾加入nums[i]的新得分为pre2+nums[i]。由于nums[i]是偶数，因此需维护pre2的值，pre2=max(pre2+nums[i],pre1+nums[i]-x)。则此时ans=max(ans,pre2)。
class Solution {
public:
long long maxScore(vector<int>& nums, int x) {
long long ans=0,pre1=0,pre2=0;
int N=nums.size();
if(nums[0]%2) pre2=-x;
else pre1=-x;
for(int i=0;i<N;++i){
if(nums[i]%2) pre1=max(pre1+nums[i],pre2+nums[i]-x);
else pre2=max(pre2+nums[i],pre1+nums[i]-x);
ans=max(pre1,pre2);
}
return ans;
}
};
