数上动态规划

算法思路

设序列中的最大值为 $M$。枚举公约数 $d$，其中 $1 \le d \le M$。

对于每个 $d$，扫描整个序列，将所有能被 $d$ 整除的数相加，得到 $T_{d}$。由于所有元素均为正数，这样可以得到由 $d$ 的倍数组成的选择方案中的最大元素和。

将答案初始化为 $0$，每次用 $d \times T_{d}$ 更新答案，最后输出最大值。

注意，这些数的实际最大公约数可能大于 $d$，但不会影响最终答案的正确性。

正确性证明

对于任意 $d$，若选出了至少一个数，则这些数的实际最大公约数 $H$ 满足 $H \ge d$。因此，候选值 $d \times T_{d}$ 不超过该选择方案的真实价值，也就不会超过最优值。若没有选出任何数，则候选值为 $0$，同样不会超过最优值。

设最优方案的元素和为 $S$，最大公约数为 $G$。这些元素都能被 $G$ 整除。由于所有元素均为正数，枚举到 $d=G$ 时，有 $T_{G} \ge S$，因此候选值 $G \times T_{G}$ 不小于最优值 $G \times S$。

综上，算法既不会高估答案，也不会遗漏最优值，因此算法正确。

复杂度分析

共枚举 $M$ 个公约数，每次扫描 $n$ 个元素，时间复杂度为 $O(nM)$，其中 $M \le 1000$。

存储序列需要 $O(n)$ 空间，除此之外只需要 $O(1)$ 的额外空间。