会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
题目要求从给定序列中选出一个 和谐子序列（长度至少为 1，且除长度为 1 外，任意相邻两项之和均为 3 的倍数），使得子序列的元素总和最大。由于子序列不要求连续，只需保持原序，我们可以根据元素模 3 的余数进行分类讨论。
关键观察
- 设元素 x 模 3 的余数为 0,1,2。两项之和能被 3 整除，等价于余数对为 (0,0)、(1,2) 或 (2,1)。
- 余数为 0 的元素：只能与同为余 0 的元素相邻。因此，想要在和谐子序列中包含余 0 元素，该子序列必须全部由余 0 的元素构成。由于所有元素均为正整数，直接取所有余 0 元素一定是最优的，令其总和为 S0。
- 余数为 1 或 2 的元素：必须按 1↔2 交替出现，不能连续出现相同的非 0 余数，也不能中途插入余 0 的元素。因此，最优的和谐子序列要么全由余 0 组成，要么由余 1 和余 2 交替组成。
