思路

• 关键观察：

  • 设元素按模 $3$ 的余数为 $0,1,2$。相邻两项之和能被 $3$ 整除，当且仅当余数对为 $(0,0),(1,2),(2,1)$。
  • 若子序列包含余数为 $0$ 的元素，则相邻也只能是 $0$。因此包含 $0$ 余数的三好子序列只能全部由余数为 $0$ 的元素组成。
  • 含有余数为 $1,2$ 的三好子序列必须在 $1$ 与 $2$ 之间交替。

• 因此最大和来源只有两类：

题目内容

给定一个由 $n$ 个整数构成的数组 {$a_1,a_2,…,a_n$} 。

如果一个子序列的长度为 $1$ 、或其任意相邻两项之和均为 $3$ 的倍数，则称其为 三好子序列 。