#P2021092. 非零段划分
非零段划分
非零段划分
题目描述
题目描述
A1,A2,⋯,An是一个由n个自然数(非负整数)组成的数组。我们称其中Ai,⋯,Aj是一个非零段,当且仅当以下条件同时满足:
1≤i≤j≤n;
对于任意的整数k,若i≤k≤j,则Ak>0;
i=1或Ai−1=0;
j=n或Aj+1=0。
下面展示了几个简单的例子:
A=[3,1,2,0,0,2,0,4,5,0,2]中的4个非零段依次为[3,1,2]、[2]、[4,5]和[2];
A=[2,3,1,4,5]仅有1个非零段;
A=[0,0,0]则不含非零段(即非零段个数为0)。
现在我们可以对数组A进行如下操作:任选一个正整数p,然后将A中所有小于p的数都变为0。试选取一个合适的p,使得数组A中的非零段个数达到最大。若输入的A所含非零段数已达最大值,可取p=1,即不对A做任何修改。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数n。
输入的第二行包含n个用空格分隔的自然数A1,A2,⋯,An。
输出格式
输出到标准输出。
仅输出一个整数,表示对数组A进行操作后,其非零段个数能达到的最大值。
数据范围
(原站未提供,导入后需人工补齐)
样例
11
3 1 2 0 0 2 0 4 5 0 2
5
样例1解释
p=2时,A=[3,0,2,0,0,2,0,4,5,0,2],5个非零段依次为[3]、[2]、[2]、[4,5]和[2];此时非零段个数达到最大。
14
5 1 20 10 10 10 10 15 10 20 1 5 10 15
4
样例2解释
p=12时,A=[0,0,20,0,0,0,0,15,0,20,0,0,0,15],4个非零段依次为[20]、[15]、[20]和[15];此时非零段个数达到最大。
3
1 0 0
1
样例3解释
p=1时,A=[1,0,0],此时仅有1个非零段[1],非零段个数达到最大。
3
0 0 0
0
样例4解释
无论p取何值,A都不含有非零段,故非零段个数至多为0。
提示
子任务
70%的测试数据满足n≤1000;
全部的测试数据满足n≤5×10^5,且数组A中的每一个数均不超过10^4。