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

P3484.第1题-三好子序列

1000ms

Difficulty: 4

所属公司 : 阿里

算法与标签>动态规划

题目内容

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

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

请你从原数组中选出一个三好子序列，使其元素之和最大，输出该最大和。

【名词解释】子序列：指从原序列中删除若干元素后，保持相对顺序得到的新序列。

第一行输入一个整数 $n(1 ≦n ≦2×10^5)$ ，表示数组的长度。第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≦a_i≦ 10^6)$ ，表示数组元素。

输出一个整数，表示最大三好子序列的元素和。

输入

6
1 1 4 5 1 4

输出

说明

在数组 { $1,1,4,5,1,4$ } 中，所有满足任意相邻两项之和为 $3$ 的倍数的子序列中，和最大的三好子序列为 { $4,5,4$ } ，它对应原序列下标 { $3,4,6$ } ，其元素和为 $4+5+4=13$ 。

输入

预期输出（选填）