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

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

题目描述

n 个魔法石围成一个环形（即第 n 个魔法石与第 1 个魔法石相邻），每个魔法石蕴含一定的能量值（整数，可正可负）。法师需要选择一段连续的魔法石（至少选择 1 个，可以跨越首尾），收集它们的能量，要求收集的总能量能被 k 整除，且总能量值尽可能大。

请计算满足条件的最大总能量值。如果无法找到任何满足条件的收集方案（即不存在能被 k 整除的连续子数组和），则输出数字 0。

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

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

输入描述

• int[] nums n 个整数，表示每个魔法石的能量值（按顺时针顺序）
• int n 魔法石数量
• int k 除数

输出描述

一个整数，表示能被 k 整除的最大总能量值；如果不存在，输出数字 0。

数据范围

1. 1≤n≤2×105
2. 1≤k≤1000
3. −106≤ 能量值 ≤106

要求

• 时间复杂度: O(n) 或 O(nlogn)
• 空间复杂度: O(n)

示例1

输入

[1,2,3,4,5],5,3

输出

15

说明

选择全部 5 个魔法石，总和为 15，能被 3整除，且这是所有能被 3 整除的连续子数组和中最大的（如 3、6、9、12 等都小于 15）

示例2

输入

[3,-1,2,4,-2,5],6,4

输出

12

说明

选择 [3,−1,2,4,−2,5] 总和为 11；

选择 [4,−2,5,3] 和为 10；

选择 [2,4,−2,5,3] 和为 12，能被 4 整除，且为最大值

解题思路

本题是前缀和 + 单调队列的经典应用，解决环形数组最大子数组和（能被k整除）问题。

关键观察：

1. 环形数组问题：将数组复制一倍处理
2. 子数组和 = 前缀和之差
3. 能被k整除：两前缀和同余
4. 找最大和：同余情况下前缀和差最大

算法步骤

1. 前缀和：计算累积和
2. 余数分组：按 k 的余数维护单调队列
3. 窗口滑动：保持窗口大小不超过n
4. 计算答案：prefix - min_prefix

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n