本文主要是介绍力扣-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 。
思路
题目要求最大值，每一次有两种选择方法，一种是下一个奇偶不同要减去X(题目给的固定值)，一种是选择奇偶相同的不用减，这里就需要做抉择，选择不同会减但不一定就比奇偶相同的小。可以建立一个表用倒序的方法将区间得到的分数记录下来，分为两种，一种是奇偶相同一种是奇偶不同。
解题方法
建立一个dp表f[i][j]，i表示区间的起点，终点为都为n-1。j表示该i-n-1序列的数字的奇偶性，1为奇，0为偶。（当j的奇偶性于num[i]不同时，意味着没有选择num[i]）
注意一定要倒序即从n-1开始，保证最后一定有起点0，不然正序无法保证最后一定有起点0。相当于，后面得出的结果都是为了前者更好的 选择且有得选，如dp[0][0]肯定要考率d[i+1][0]d[i+1][1]
代码
class Solution {public long maxScore(int[] nums, int x) {int n=nums.length;long[][] f= new long[n+1][2];for(int i=n-1;i>=0;i--){int v=nums[i];int r=v%2;f[i][r^1]=f[i+1][r^1];f[i][r]=Math.max(f[i+1][r],f[i+1][r^1]-x)+v;}return f[0][nums[0]%2];}
}这篇关于力扣-2786的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
