邯郸做网站推广的公司,wordpress 论坛小程序,最近新闻热点,论述网站建设引言Leetcode 2786. 访问数组中的位置使分数最大 给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。 你 一开始 在数组的位置 0 处#xff0c;你可以按照下述规则访问数组中的其他位置#xff1a; 如果你当前在位置 i #xff0c;那么你可以移动到满足 i j 的 任意 …Leetcode 2786. 访问数组中的位置使分数最大 给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。 你 一开始 在数组的位置 0 处你可以按照下述规则访问数组中的其他位置 如果你当前在位置 i 那么你可以移动到满足 i j 的 任意 位置 j 。对于你访问的位置 i 你可以获得分数 nums[i] 。如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同那么你将失去分数 x 。 请你返回你能得到的 最大 得分之和。 注意 你一开始的分数为 nums[0] 。 定义一个数组保存到当前位置且包含当前位置的最大分数每判断一个元素是遍历之前的元素进行累加得到最大的分数。完整代码
class Solution {public long maxScore(int[] nums, int x) {int n nums.length;long res nums[0];long[] val new long[n];val[0] nums[0];for (int i 1; i n; i) {long max nums[i];for (int j 0; j i; j) {long t val[j] (long) nums[i];if ((nums[j] % 2) ! (nums[i] % 2)) t - x;max Math.max(max, t);}val[i] max;res Math.max(res, val[i]);}return res;}
}但注意一开始处于 0 处所以需要从 0 开始上述代码是可以不从 0 开始从自己开始因此值会偏大。将当前元素的初始值初始化为 Long.MIN_VALUE那么从前面开始就比从自己开始小因此就能避免从自己开始。完整代码
class Solution {public long maxScore(int[] nums, int x) {int n nums.length;long res nums[0];long[] val new long[n];val[0] nums[0];for (int i 1; i n; i) {long max Long.MIN_VALUE;for (int j 0; j i; j) {long t val[j] (long) nums[i];if ((nums[j] % 2) ! (nums[i] % 2)) t - x;max Math.max(max, t);}val[i] max;res Math.max(res, val[i]);}return res;}
}以上的时间复杂度为 O ( n 2 ) O(n^2) O(n2)因为每次都要遍历前面的结果。保存前面的最优结果它的最优结果就两种情况
最优结果的最后一个元素是奇数最优结果的最后一个元素是偶数
完整代码
class Solution {public long maxScore(int[] nums, int x) {int n nums.length;long res nums[0];long[] dp new long[]{Integer.MIN_VALUE, Integer.MIN_VALUE};dp[nums[0] % 2] nums[0];for (int i 1; i n; i) {int part nums[i] % 2;long cur Math.max(dp[part] nums[i], dp[1 - part] nums[i] - x);res Math.max(res, cur);dp[part] Math.max(dp[part], cur);}return res;}
}要注意最小值的设置因为里面存在 -x可能会超出最小值的范围因此可以设置为 -x或 Integer.MIN_VALUE。
