题目理解

我们需要从 $n$ 个正整数中选出三个不同的数 $a_i, a_j, a_k$，使得 $(a_i + a_j) \bmod a_k$ 的值最大。

关键观察

1. 模运算的性质

对于 $(a_i + a_j) \bmod a_k$，有：

• 如果 $a_i + a_j < a_k$，那么结果就是 $a_i + a_j$
• 如果 $a_i + a_j \ge a_k$，那么结果就是 $a_i + a_j - a_k$

2. 优化思路

• 当 $a_k$ 较大时，$a_i + a_j$ 可能小于 $a_k$，此时结果为 $a_i + a_j$
• 当 $a_k$ 较小时，$a_i + a_j$ 可能远大于 $a_k$，此时结果为 $a_i + a_j - a_k$

算法设计

1. 排序与去重

首先对数组进行排序，这样可以方便地找到较大的数值。

2. 枚举模数 $a_k$

从大到小枚举可能的模数 $a_k$，如果当前答案已经大于等于 $a_k - 1$，那么后续的 $a_k$ 不可能产生更大的答案。

3. 处理余数数组

对于每个候选的 $a_k$：

• 计算其他所有数对 $a_k$ 取模的结果
• 对余数数组进行排序
• 考虑两种情况：
  1. 最大的两个余数相加（可能小于 $a_k$）
  2. 使用双指针寻找最接近 $a_k$ 的余数对

算法正确性

1. 剪枝的正确性

如果当前答案 $ans \ge a_k - 1$，那么对于所有 $x < a_k$，都有 $x \le a_k - 1 \le ans$，因此不可能得到更大的答案。

2. 双指针的正确性

排序后的余数数组使用双指针可以高效地找到最接近 $a_k$ 的余数对，从而最大化 $(a_i + a_j) \bmod a_k$ 的值。

复杂度分析

时间复杂度

• 排序：$O(n \log n)$
• 枚举模数：最坏情况下 $O(n)$ 次
• 每次处理：$O(n \log n)$（排序余数数组）

最坏情况下总复杂度为 $O(n^2 \log n)$，但由于剪枝优化，实际运行效率较高。

空间复杂度

• 存储数组：$O(n)$
• 余数数组：$O(n)$

算法标签

• 贪心
• 数论
• 排序
• 双指针扫描
• 模运算

总结

本题通过巧妙的排序和剪枝策略，将看似需要三重循环的暴力枚举优化为高效的算法。关键在于观察到当模数较大时答案的潜在上限，以及利用双指针技术快速寻找最优的余数对组合。