python解CCFCSP真题《2021092—非零段划分》

题目描述

A1,A2,⋯,An 是一个由 n 个自然数&＃xff08;非负整数&＃xff09;组成的数组。我们称其中 Ai,⋯,Aj 是一个非零段&＃xff0c;当且仅当以下条件同时满足&＃xff1a;

• 1≤i≤j≤n&＃xff1b;
• 对于任意的整数 k&＃xff0c;若 i≤k≤j&＃xff0c;则 Ak>0&＃xff1b;
• i&＃61;1 或 Ai−1&＃61;0&＃xff1b;
• j&＃61;n 或 Aj&＃43;1&＃61;0。

下面展示了几个简单的例子&＃xff1a;

• A&＃61;[3,1,2,0,0,2,0,4,5,0,2] 中的 4 个非零段依次为 [3,1,2]、[2]、[4,5] 和 [2]&＃xff1b;
• A&＃61;[2,3,1,4,5] 仅有 1 个非零段&＃xff1b;
• A&＃61;[0,0,0] 则不含非零段&＃xff08;即非零段个数为 0&＃xff09;。

现在我们可以对数组 A 进行如下操作&＃xff1a;任选一个正整数 p&＃xff0c;然后将 A 中所有小于 p 的数都变为 0。试选取一个合适的 p&＃xff0c;使得数组 A 中的非零段个数达到最大。若输入的 A 所含非零段数已达最大值&＃xff0c;可取 p&＃61;1&＃xff0c;即不对 A 做任何修改。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 n。

输入的第二行包含 n 个用空格分隔的自然数 A1,A2,⋯,An。

输出格式

输出到标准输出。

仅输出一个整数&＃xff0c;表示对数组 A 进行操作后&＃xff0c;其非零段个数能达到的最大值。

样例1输入

11
3 1 2 0 0 2 0 4 5 0 2

样例1输出

5

样例1解释

p&＃61;2 时&＃xff0c;A&＃61;[3,0,2,0,0,2,0,4,5,0,2]&＃xff0c;5 个非零段依次为 [3]、[2]、[2]、[4,5] 和 [2]&＃xff1b;此时非零段个数达到最大。

样例2输入

14
5 1 20 10 10 10 10 15 10 20 1 5 10 15

样例2输出

4

样例2解释

p&＃61;12 时&＃xff0c;A&＃61;[0,0,20,0,0,0,0,15,0,20,0,0,0,15]&＃xff0c;4 个非零段依次为 [20]、[15]、[20] 和 [15]&＃xff1b;此时非零段个数达到最大。

样例3输入

3
1 0 0

样例3输出

1

样例3解释

p&＃61;1 时&＃xff0c;A&＃61;[1,0,0]&＃xff0c;此时仅有 1 个非零段 [1]&＃xff0c;非零段个数达到最大。

样例4输入

3
0 0 0

样例4输出

0

样例4解释

无论 p 取何值&＃xff0c;A 都不含有非零段&＃xff0c;故非零段个数至多为 0。

子任务

70% 的测试数据满足 n≤1000&＃xff1b;

全部的测试数据满足 n≤5×105&＃xff0c;且数组 A 中的每一个数均不超过 104。