Skill执行链完整性检测

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

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

题目描述

在 AI 助手的技能系统中，执行链由多个 Skill 按顺序排列。每个 Skill 有一个类型标记：

• type[i]=0: 基础类型 Skill，无依赖，可以独立执行
• type[i]=1: 扩展类型 Skill，依赖前一个 Skill 执行
• type[i]=2: 高级类型 Skill，依赖前两个 Skill 执行

执行链的完整性规则：

1. 首元素限制：执行链不能以扩展类型（type=1）或高级类型（type=2）开头，必须以基础类型（type=0）开头

2. 依赖传递：

• 扩展类型（type=1）的直接前驱必须是基础类型（type=0）
• 高级类型（type=2）的前驱和前前驱都必须是基础类型（type=0）

3. 链式依赖：每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型

给定一个类型数组 type，找到最长的连续 Skill 子链，使得子链满足完整性规则。返回该子链的长度。

数据规模

• 0 ≤ type.length ≤ 2000

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

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

输入描述

类型数组 type

输出描述

该子链的长度

示例1

输入

[0,0,0]

输出

3

说明

全为基础类型,满足规则(不违反任何约束)

示例2

输入

[0,1,0,1]

输出

4

说明

0→1✓ (基础后接扩展)

1→0✓(扩展后接基础)

0→1✓(基础后接扩展)

无违反规则,整个链有效

示例3

输入

[2,0,0]

输出

2

说明

首元素高级类型违规，从位置 1 开始 [0,0] 长度 2

示例4

输入

[0,1,0,0,2]

输出

5

说明

0→1✓(基础后接扩展)

1→0✓(扩展后接基础)

0→0✓ (基础后接基础)

0→0→2✓ (基础、基础后接高级)

解题思路

本题是一个动态规划问题，核心在于维护以不同类型结尾的最长有效链长度。

关键观察：1. 基础类型(type=0)可以独立成链，也可以接在任何有效链后面 2. 扩展类型(type=1)必须以前一个基础类型为直接前驱 3. 高级类型(type=2)必须以前两个都是基础类型为直接前驱

状态定义

定义三个动态规划变量： -dp0: 以基础类型结尾的最长有效链长度 -dp1: 以扩展类型结尾的最长有效链长度 -dp2: 以高级类型结尾的最长有效链长度

状态转移

若type[i]==0(基础类型):nd0=1#独立成链nd0=max(nd0,dp0+1,dp1+1,dp2+1)#接在前面的有效链后面若type[i]==1(扩展类型):nd1=dp0+1#必须以前一个基础类型为前驱若type[i]==2(高级类型):nd2=dp0+1#必须以前两个基础类型为前驱

复杂度分析

• 时间复杂度: O(n)，只需遍历一次数组
• 空间复杂度: O(1)，只使用常数个变