← 返回题目列表

AtCoder · joi2013ho1

1. 照明

中文机器翻译题面 查看原题

配点: 100 点

每年的JOI高中学园祭,走廊都会被灯光装饰。照度为 它由 N 个灯泡组成,灯泡从走廊的西侧到东侧排成一排。每个灯泡要么打开,要么关闭。

JOI 高中仓库里有一台操作灯泡的机器。当本机在灯光装饰中指定连续的灯泡时,所有指定的点亮的灯泡将被关闭,而所有未点亮的灯泡将被打开。但由于机器老化, 只能使用1 次。

JOI 高中生正在学习如何制作成排的灯泡,这些灯泡在点亮和熄灭之间交替。 我喜欢交互列)。因此,如果您需要这台机器, 我决定仅使用 1 次来创建包含尽可能多的交替行的照明。

例

例如,灯光的排列是从西向东。

○ ○ ● ● ○ ● ○ ○ ○ ●

(○代表灯泡亮,●代表灯泡不亮)。 此时,4 起 件数最多为 7 当使用 4 灯泡操作机器时,

○ ○ ● ○ ● ○ ● ○ ○ ●

变为2 起 件数最多为 8 灯泡的长度是 形成 7 的交替序列。

○ ○ ● ○ ● ○ ● ○ ○ ●

另外, 如果我们只为第8 个灯泡操作机器, 直到

○ ○ ● ● ○ ● ○ ● ○ ●

变为4 起 件数最多为 10 的灯泡形成长度为 7 的交替行。

○ ○ ● ● ○ ● ○ ● ○ ●

最大化机器 通过使用 1 次,长度变为 无法创建超过 8 个交替列。

課題

当给出有关照明的信息时,机器设置为最大 1 编写一个程序,求使用一次灯泡获得的灯泡阵列中包含的交替行的最大可能长度。

制限

2 \leqq N \leqq 100\,000  构成照明的灯泡数量

入力

从标准输入读取以下数据。

  • 1 行是整数 N 被写下了。
  • 第二行说 N 的 您可以创建一个包含 0 或 至少 1 以空格作为分隔符。每个整数代表操作机器之前有关灯泡的信息。从左边开始 i (1 \leqq i \leqq N) 从西数第一个整数 代表第 i 个灯泡的信息,整数为 1 然后灯泡亮了,0 表示灯不亮。

出力

将标准输出设置为一个整数,表示可以创建的交替灯泡行的最大长度。 输出为 1 行输出。

採点基準

评分数据中,分配的分数 20 对于%,N \leqq 500 很满意。

评分数据中,分配的分数 40 对于%,N \leqq 2\,000 很满意。


入力例 1

10
1 1 0 0 1 0 1 1 1 0

出力例 1

7

这是问题文本中解释的示例。


入力例 2

10
1 0 0 0 0 1 0 1 0 1

出力例 2

8

从西边 如果仅操作第 4 个灯泡,则最大值 获得满足 8 的交替序列。


入力例 3

5
1 1 0 1 1

出力例 3

5

从西边算起 通过操作最多 2 起 件数最多为 4 个灯泡,您可以创建所有灯泡的交替行。


入力例 4

3
0 1 0

出力例 4

3

请注意,有时您不需要使用机器。