力扣每日一题（2024-06-14）2786. 访问数组中的位置使分数最大

本文主要是介绍力扣每日一题（2024-06-14）2786. 访问数组中的位置使分数最大，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考官方题解2786. 访问数组中的位置使分数最大 - 力扣（LeetCode）

问题描述

给定一个下标从 0 开始的整数数组 nums 和一个正整数 x。你一开始在数组的第 0 个位置，你可以移动到满足 i < j 的任意位置 j。如果你访问的位置 i，你可以获得分数 nums[i]。如果从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的奇偶性不同，那么你将失去分数 x。请返回你能得到的最大得分之和。

动态规划思想

我们需要用动态规划来解决这个问题，通过维护一个状态数组来记录在不同奇偶性下的最大得分。具体地：

1. 状态定义：

   • dp[0] 表示当前最后一个元素为偶数时的最大得分。

   • dp[1] 表示当前最后一个元素为奇数时的最大得分。

2. 状态初始化：

   • 初始情况下，你在位置 0，所以得分为 nums[0]。

   • 根据 nums[0] 的奇偶性，初始化对应的 dp 值。

3. 状态转移： 对于数组中的每一个元素 nums[i]，计算当前元素为奇数或偶数的情况下的最大得分。

   • 如果 nums[i] 是偶数，parity = 0；

   • 如果 nums[i] 是奇数，parity = 1。

   • cur 表示当前最大得分，可以通过两种方式计算得到：

     1. 当前元素与上一个同奇偶性，则得分为 dp[parity] + nums[i]。

     2. 当前元素与上一个不同奇偶性，则得分为 dp[1 - parity] + nums[i] - x。

   • 更新 dp[parity] 为当前奇偶性情况下的最大得分。

   • 更新 res 为当前最大得分。

4. 返回结果： 返回最终最大得分 res。

代码详解

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];  // 初始化 dp，依据第一个元素的奇偶性for (int i = 1; i < nums.length; i++) {// 计算当前元素的奇偶性int parity = nums[i] % 2;  // 计算当前最大得分long cur = Math.max(dp[parity] + nums[i], dp[1 - parity] + nums[i] - x);  // 更新 res = Math.max(res, cur);  dp[parity] = Math.max(dp[parity], cur); }return res;}
}

这篇关于力扣每日一题（2024-06-14）2786. 访问数组中的位置使分数最大的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---