2026 华为OD机试真题9月6日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

山路一共设有 n 个关卡，按 1∼n 顺序排列。当前位于 1 号关卡，必须按照关卡从小到大闯关，且必须到达最后第 n 号关卡才算寻宝成功。每个关卡都有对应的宝藏分值(可能为负数)，经过当前关卡即可获得该关卡分值，分数持续累加。

移动规则：

1. 从当前关卡，下一次只能在前方 1 关或者 2 关处打卡；
2. 限制规则：不能连续两次都一次性跳 2 关，违反该规则的路线无效；

请求出：所有合法路线中，能够收集到的最大累加总分。

2026 华为OD机试真题9月6日华为OD上机新系统考试真题 100 分题型

输入描述

参数1：整数 n，代表关卡数量

参数2：整数数组，依次表示第 1∼n 关的宝藏分值

1≤n≤20

每关分值：−999≤val≤999

输出描述

输出一个整数，代表合法路线的最大累加得分。

示例1

输入

5
10,5,8,3,15

输出

41

说明

• 合法路线示例：1→2→3→4→5，无连续跳两关，总分：10+5+8+3+15=41
• 路线 1→3→5 连续两次跳 2 关，违规，不计入统计。

示例2

输入

4
10,1,1,100

输出

112

说明

• 路线 1→2→3→4 (1,1,1): 10+1+1+100=112
• 路线 1→3→4 (2,1): 10+1+100=111
• 路线 1→2→4 (1,2): 10+1+100=111
• 最大值 112。

解题思路

核心思想

每次只能向前跳 1 关或 2 关，并且不能连续两次都跳 2 关。为了判断下一跳是否合法，状态中必须记录“上一次跳了几关”。

定义两个状态，并用滚动变量保存：

• oneStep：到达当前关卡时，上一次跳 1 关的最大得分；
• twoStep：到达当前关卡时，上一次跳 2 关的最大得分。

计算第 i 关时，如果最后一步跳 1 关，则可以从第 i-1 关的两种状态转移而来；如果最后一步跳 2 关，则只能从第 i-2 关且上一跳为 1 关的状态转移而来。由于每次只依赖前一关和前两关的少量状态，可以把空间优化到常数级。

算法步骤

1. 起点为第 1 关，先获得第 1 关分值。
2. 维护上一关的 prevOne、prevTwo，分别表示最后跳 1 关和最后跳 2 关到达上一关的最大得分。
3. 额外维护 prevPrevOne，表示最后跳 1 关到达前两关位置的最大得分。
4. 从第 2 关开始向后扫描：
   • curOne = max(prevOne, prevTwo) + score[i]；
   • curTwo = prevPrevOne + score[i]，且只在 i >= 2 时有效。
5. 滚动更新状态，最终返回最后一关两种状态中的较大值。

复杂度分析

设关卡数量为 n。

• 时间复杂度：O(n)
• 空间复杂度：`O