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

【LetMeFly】2786.访问数组中的位置使分数最大：奇偶分开记录（逻辑还算清晰的题解）

力扣题目链接：https://leetcode.cn/problems/visit-array-positions-to-maximize-score/

给你一个下标从 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 <= 105
• 1 <= nums[i], x <= 106

解题方法：两个变量分别记录上一个位置是奇数和偶数时的最大值

每个数都大于0，并且奇偶性相同的数之间跳跃没有额外的费用（不用-x）。因此奇偶性相同的数不会间隔地跳：

以奇数为例，假设有三个奇数$a$、$b$、$c$，则由奇数跳到$c$的话，一定是从$b$跳过去的，不可能是从$a$直接跳到$c$。因为$a->c$不如$a->b->c$。

因此，我们只需要使用两个变量$odd$和$even$，分别记录上一个数为奇数或偶数时的分数最大值。遍历整数数组时有如下公式：

• 若当前元素$t$为奇数，则从奇数跳过来的话分数为$odd+t$，从偶数跳过来的话分数为$even+t-x$，因此最大分数为$\max(odd+t, even+t-x)$
• 若当前元素$t$为偶数，则从奇数跳过来的话分数为$odd+t-x$，从偶数跳过来的话分数为$even+t$，因此最大分数为$\max(odd+t-x, even+t)$

特别的，起点必须为第一个数。假设第一个数为奇数，则偶数的默认值为$-x$。这是因为：

第一个数为奇数的话，第一次跳到偶数的时候，实质上必定是由奇数跳过去的。而计算公式中的$even+t$是由偶数跳过去的，相当于少扣了$x$分。

时空复杂度分析

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

typedef long long ll;
class Solution {
public:
    ll maxScore(vector<int>& nums, int x) {
        ll odd = nums[0] % 2 ? 0 : -x, even = nums[0] % 2 ? -x : 0;
        for (int t : nums) {
            if (t % 2) {
                odd = max(odd + t, even + t - x);
            }
            else {
                even = max(odd + t - x, even + t);
            }
        }
        return max(odd, even);
    }
};

Go

func max(a int64, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func maxScore(nums []int, x int) int64 {
    odd, even := int64(0), int64(0)
    if nums[0] % 2 == 0 {
        odd = -int64(x)
    } else {
        even = -int64(x)
    }
    for _, t := range nums {
        if t % 2 != 0 {
            odd = max(odd + int64(t), even + int64(t) - int64(x))
        } else {
            even =  max(odd + int64(t) - int64(x), even + int64(t))
        }
    }
    return max(odd, even)
}

Java

class Solution {
    public long maxScore(int[] nums, int x) {
        long odd = nums[0] % 2 != 0 ? 0 : -x, even = nums[0] % 2 != 0 ? -x : 0;
        for (int t : nums) {
            if (t % 2 != 0) {
                odd = Math.max(odd + t, even + t - x);
            }
            else {
                even = Math.max(odd + t - x, even + t);
            }
        }
        return Math.max(odd, even);
    }
}

Python

# from typing import List

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        odd, even = 0 if nums[0] % 2 else -x, -x if nums[0] % 2 else 0
        for t in nums:
            if t % 2:
                odd = max(odd + t, even + t - x)
            else:
                even = max(odd + t - x, even + t)
        return max(even, odd)

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/139688753