做外贸业务去哪些网站,php 除了做网站,惠州网站建设优化,wordpress设计页面教程Leetcode 2786. 访问数组中的位置使分数最大
DP 以每个位置为结尾的序列的分数取决于前方的分数#xff0c;根据奇偶性计算#xff0c;取最大值 超时
class Solution {public long maxScore(int[] nums, int x) {int n nums.length;long dp[] new long[n];Arrays.fill(dp…Leetcode 2786. 访问数组中的位置使分数最大
DP 以每个位置为结尾的序列的分数取决于前方的分数根据奇偶性计算取最大值 超时
class Solution {public long maxScore(int[] nums, int x) {int n nums.length;long dp[] new long[n];Arrays.fill(dp, Integer.MIN_VALUE);dp[0] nums[0];long res nums[0];for(int i 1; i n; i ){for(int j 0; j i; j ){if(nums[j] % 2 nums[i] % 2){dp[i] Math.max(dp[i], dp[j] nums[i]);}else{dp[i] Math.max(dp[i], dp[j] nums[i] - (long)x);}}res Math.max(res, dp[i]);}return res;}
}优化
对于 nums[ i ] 来说该位置的分数取决于前方的序列分数分为上一个选择是奇数和偶数两种情况只需max0、max1来分别记录前方的奇偶两种情况最值即可计算出当前位置的分数最值
避免思维误区计算cur时考虑的不是选或不选的两种情况而是必定选择 nums[ i ] 作为序列最后一个元素时取前方奇偶两种可能所获得的分数哪一种更大
由于存在x值较大的情况计算中可能出现负数将max0、max1初始化为INT_MIN
获取最值后根据 nums[ i ] 的奇偶性选择更新max0或max1 计算max0/1的两种可能时即使有可能异性-x后的分数更大但由于存在同性计算 — 两个正数相加因此max0/1的值必定会增大直接将cur赋值给max0/1
class Solution {public long maxScore(int[] nums, int x) {int n nums.length;long max0 Integer.MIN_VALUE; // 前方偶数结尾的最大分数long max1 Integer.MIN_VALUE; // 前方奇数结尾的最大分数if(nums[0] % 2 0)max0 nums[0];elsemax1 nums[0];long res nums[0];for(int i 1; i n; i ){long cur;if(nums[i] % 2 0){cur Math.max(max0 nums[i], max1 nums[i] - x);max0 cur;// max0 Math.max(max0, cur);// 同性情况max0nums[i]正数求和计算导致cur必然大于max0省去Max计算}else{cur Math.max(max0 nums[i] - x, max1 nums[i]);max1 cur;}res Math.max(res, cur);}return res;}
}
