2786. 访问数组中的位置使分数最大

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

题目

给你一个下标从 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 <= 10^5
1 <= nums[i], x <= 10^6

代码

完整代码

#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>// 函数判断是否为奇数
bool isOdd(int num) {return num % 2 != 0;
}long long maxScore(int* nums, int numsSize, int x) {long long *dp = (long long *)calloc(numsSize, sizeof(long long));// 初始化dp数组for (int i = 0; i < numsSize; i++) {dp[i] = LLONG_MIN;}dp[0] = nums[0];long long score = nums[0];for (int i = 0; i < numsSize; i++) {for (int j = i + 1; j < numsSize; j++) {long long potentialScore = dp[i] + nums[j];if (isOdd(nums[i]) != isOdd(nums[j])) {potentialScore -= x;}if (potentialScore > dp[j]) {dp[j] = potentialScore;if (dp[j] > score) {score = dp[j];}}}}free(dp);return score;
}

思路分析

该问题可以通过动态规划来解决。我们需要一个动态规划数组 dp，其中 dp[i] 表示到达位置 i 的最大得分。

初始化

定义一个布尔函数 isOdd 来判断一个数是否为奇数。
初始化动态规划数组 dp，其长度为 numsSize，初始值为 LLONG_MIN。
将 dp[0] 初始化为 nums[0]，因为起始位置为 0。

动态规划转移

遍历数组，从位置 i 到位置 j (i < j)，计算从位置 i 到位置 j 的潜在得分 potentialScore。
如果 nums[i] 和 nums[j] 的奇偶性不同，则减去分数 x。
如果 potentialScore 大于 dp[j]，更新 dp[j] 和最大得分 score。

拆解分析

初始化函数和动态规划数组

bool isOdd(int num) {return num % 2 != 0;
}long long *dp = (long long *)calloc(numsSize, sizeof(long long));
for (int i = 0; i < numsSize; i++) {dp[i] = LLONG_MIN;
}dp[0] = nums[0];
long long score = nums[0];

遍历数组更新动态规划数组

for (int i = 0; i < numsSize; i++) {for (int j = i + 1; j < numsSize; j++) {long long potentialScore = dp[i] + nums[j];if (isOdd(nums[i]) != isOdd(nums[j])) {potentialScore -= x;}if (potentialScore > dp[j]) {dp[j] = potentialScore;if (dp[j] > score) {score = dp[j];}}}
}