思路

• 关键观察：

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

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

  1. 全部取余数为 $0$ 的元素（都为正数，直接全取）：记为 $S_0$；
  2. 只从余数为 $1$ 与 $2$ 的元素中选取，且按 $1\leftrightarrow2$ 交替，最大权值子序列。

• 交替子序列可用线性 DP 解决： 设

  

  扫描每个元素 $x$：

  • 若 $x\bmod 3=0$：累加到 $S_0$。

  • 若 $x\bmod 3=1$：更新

    $$dp_1 \leftarrow \max(dp_1,\ x,\ dp_2+x).$$

  • 若 $x\bmod 3=2$：更新

    $$dp_2 \leftarrow \max(dp_2,\ x,\ dp_1+x).$$

  最终答案为 $\max(S_0, dp_1, dp_2)$。时间复杂度 $O(n)$，空间复杂度 $O(1)$。

正确性要点

• 余数为 $0$ 的元素之间两两相邻之和仍为 $3$ 的倍数，且全为正，故最优即全部取之。
• 余数为 $1,2$ 的部分只能交替连接，DP 正是对“接到对方余数末尾”或“单独开新序列”的最优子结构刻画。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	if (!(cin >> n)) return 0;
	long long S0 = 0; // 余数为0的元素总和
	const long long NEG = LLONG_MIN / 4; // 负无穷哨值，防溢出
	long long dp1 = NEG, dp2 = NEG; // 以余数1/2结尾的最大和

	for (int i = 0; i < n; ++i) {
		long long x; cin >> x;
		int r = (int)(x % 3);
		if (r == 0) {
			// 全为正数，余0可全部取
			S0 += x;
		} else if (r == 1) {
			long long cand = x; // 新开序列
			if (dp2 != NEG) cand = max(cand, dp2 + x); // 接在以2结尾后
			dp1 = max(dp1, cand);
			dp1 = max(dp1, x); // 再次确保至少可取自身
		} else { // r == 2
			long long cand = x; // 新开序列
			if (dp1 != NEG) cand = max(cand, dp1 + x); // 接在以1结尾后
			dp2 = max(dp2, cand);
			dp2 = max(dp2, x);
		}
	}

	long long ans = S0;
	ans = max(ans, dp1);
	ans = max(ans, dp2);
	cout << ans << "\n";
	return 0;
}

Python

import sys

def main():
	data = sys.stdin.read().strip().split()
	if not data:
		return
	it = iter(data)
	n = int(next(it))
	S0 = 0  # 余数为0的元素总和
	NEG = -10**30  # 负无穷哨值
	dp1, dp2 = NEG, NEG  # 以余数1/2结尾的最大和

	for _ in range(n):
		x = int(next(it))
		r = x % 3
		if r == 0:
			# 全为正数，余0可全部取
			S0 += x
		elif r == 1:
			# 余1：可新开，或接在以2结尾后
			cand = x
			if dp2 != NEG:
				cand = max(cand, dp2 + x)
			dp1 = max(dp1, cand, x)
		else:
			# 余2：可新开，或接在以1结尾后
			cand = x
			if dp1 != NEG:
				cand = max(cand, dp1 + x)
			dp2 = max(dp2, cand, x)

	ans = max(S0, dp1, dp2)
	print(ans)

if __name__ == "__main__":
	main()

Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		if (s == null || s.isEmpty()) return;
		int n = Integer.parseInt(s.trim());
		StringTokenizer st = new StringTokenizer(br.readLine());
		long S0 = 0; // 余数为0的元素总和
		long NEG = Long.MIN_VALUE / 4; // 负无穷哨值，防溢出
		long dp1 = NEG, dp2 = NEG; // 以余数1/2结尾的最大和

		for (int i = 0; i < n; i++) {
			long x = Long.parseLong(st.nextToken());
			int r = (int)(x % 3);
			if (r == 0) {
				// 全为正数，余0可全部取
				S0 += x;
			} else if (r == 1) {
				// 余1：可新开，或接在以2结尾后
				long cand = x;
				if (dp2 != NEG) cand = Math.max(cand, dp2 + x);
				dp1 = Math.max(dp1, Math.max(cand, x));
			} else {
				// 余2：可新开，或接在以1结尾后
				long cand = x;
				if (dp1 != NEG) cand = Math.max(cand, dp1 + x);
				dp2 = Math.max(dp2, Math.max(cand, x));
			}
		}

		long ans = Math.max(S0, Math.max(dp1, dp2));
		System.out.println(ans);
	}
}

题目内容

给定一个由 $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)$ ，表示数组元素。

输出描述

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

样例1

输入

6
1 1 4 5 1 4

输出

13

说明

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