怎样做医院网站,国家对网站建设政策,小程序源码网站论坛,行业网站定位题目描述#xff1a;
给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。 你一开始 在数组的位置 0 处#xff0c;你可以按照下述规则访问数组中的其他位置#xff1a; 如果你当前在位置 i #xff0c;那么你可以移动到满足 i j 的 任意 位置 j 。 对于你访问的…题目描述
给你一个下标从 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
Leetcode题目地址
题目地址
解题思路
简单dp当前操作的最大值取决于上一操作的nums[t]是奇数还是偶数所以我们可以维护该操作前偶数的最大值和奇数的最大值。于是根据题目我们能得到如下公式 res Math.max(res, Math.max(dp[ nums[i]%2] nums[i], dp[1 - nums[i]%2] - x nums[i])) 此时记得更新dp数组的值要永远维护当前操作前的偶数的最大值和奇数的最大值 dp[nums[i]%2] Math.max(dp[nums[i]%2] nums[i], dp[1 - nums[i]%2] - x nums[i])
代码
class Solution {public long maxScore(int[] nums, int x) {long res nums[0];long[] dp {Integer.MIN_VALUE, Integer.MIN_VALUE};dp[nums[0]%2] nums[0];for(int i 1; i nums.length; i){int tmp nums[i]%2;res Math.max(res, Math.max(dp[tmp] nums[i], dp[1 - tmp] - x nums[i]));dp[tmp] Math.max(dp[tmp] nums[i], dp[1 - tmp] - x nums[i]);}return res;}
}
