Leetcode 2786. 訪問數(shù)組中的位置使分?jǐn)?shù)最大

給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 和一個(gè)正整數(shù) x 。
你 一開始 在數(shù)組的位置 0 處，你可以按照下述規(guī)則訪問數(shù)組中的其他位置：

• 如果你當(dāng)前在位置 i ，那么你可以移動到滿足 i < j 的 任意 位置 j 。
• 對于你訪問的位置 i ，你可以獲得分?jǐn)?shù) nums[i] 。
• 如果你從位置 i 移動到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你將失去分?jǐn)?shù) x 。

請你返回你能得到的 最大 得分之和。
注意 ，你一開始的分?jǐn)?shù)為 nums[0] 。

定義一個(gè)數(shù)組保存到當(dāng)前位置且包含當(dāng)前位置的最大分?jǐn)?shù)，每判斷一個(gè)元素是，遍歷之前的元素進(jìn)行累加得到最大的分?jǐn)?shù)。
完整代碼

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 開始，從自己開始，因此值會偏大。
將當(dāng)前元素的初始值初始化為 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;}
}

以上的時(shí)間復(fù)雜度為 $O(n^2)$，因?yàn)槊看味家闅v前面的結(jié)果。
保存前面的最優(yōu)結(jié)果，它的最優(yōu)結(jié)果就兩種情況：

• 最優(yōu)結(jié)果的最后一個(gè)元素是奇數(shù)
• 最優(yōu)結(jié)果的最后一個(gè)元素是偶數(shù)

完整代碼

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;}
}

要注意最小值的設(shè)置，因?yàn)槔锩娲嬖?-x，可能會超出最小值的范圍，因此可以設(shè)置為 -x或 Integer.MIN_VALUE。