[Spe]朋友

[Spe]朋友

【题目背景】
朋友?哼,有些人终成不了朋友;而朋友,真的只是时期段的吗?
【题目描述】
因比赛题目特设此题:
对于给定一个长度为 \(n\) 的序列 \(A\)(\(a_1,a_2...a_n\),首尾相连),求选择若干个不相邻数且必须选择 \(a_i\) 的情况下,所选数的和最大为多少 \(sum_i\)。(\(i∈[1,n]\))
【输入格式】
第一行一个数 \(n\)。
第二行 \(n\) 个数,为 \(a_i\)。
【输出格式】
共 \(n\) 行,每行一个数,为 \(sum_i\)。
【样例输入1】

3
-1 0 1

【样例输出1】

-1
0
1

【样例输入2】

6
-1 1 -1 -1 1 -1

【样例输出2】

0
2
0
0
2
0

【样例输入3】

7
1 2 3 4 5 6 7

【样例输出3】

11
14
15
13
15
12
15

【提示/说明】
时空限制:\(2s\),\(256MiB\)。

测试点序号 \(n\) \(\lvert a_{i}\rvert\) 特殊性质
\(1\sim 2\) \(\leq 7\) \(\leq 10\) \(N\)
\(3\sim 4\) \(\leq 3*10^3\) \(\leq 10^5\) \(N\)
\(5\sim 7\) \(\leq 2*10^5\) \(\leq 10^8\) \(Y\)
\(8\sim 10\) \(\leq 2*10^6\) \(\leq 10^8\) \(N\)

特殊性质:
\(N\):没有任何特殊性质。
\(Y\):对于 \(i∈[1,n]\),\(a_i\geq 0\)。

对于 \(100\%\) 的数据,\(3\leq n\leq 2*10^6\),\(-10^8\leq a_i\leq 10^8\)。

信息

ID
1004
难度
9
分类
(无)
标签
(无)
递交数
6
已通过
1
通过率
17%
上传者