Loading... > https://leetcode.cn/problems/visit-array-positions-to-maximize-score/description/?envType=daily-question&envId=2024-05-02 从左往右遍历数组，移动到第 $i$ 个位置所能获得的最大分数，取决于两种情况： - 最后访问的元素为奇数时候的最大值； - 最后访问的元素为偶数时候的最大值。 因此可以记录这两个数，每次对比两种情况转移过来的最大值，并更新对应奇偶性的最大值，同时统计最大的得分即可。 ```c++ class Solution { public: long long maxScore(std::vector<int>& nums, int x) { const int n = nums.size(); long long odd = INT_MIN, even = INT_MIN, res = nums[0]; nums[0] % 2 == 0 ? even = nums[0] : odd = nums[0]; for (int i = 1; i < n; i++) { if (nums[i] % 2 == 0) { even = std::max(even + nums[i], odd + nums[i] - x); } else { odd = std::max(odd + nums[i], even + nums[i] - x); } res = std::max({res, odd, even}); } return res; } }; ``` - 时间复杂度：$O(n)$ ，其中 $n$ 为数组 `nums` 的长度。 - 空间复杂度：$O(1)$ 。 最后修改：2024 年 06 月 14 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏