题目描述
A 1 , A 2 , ⋯ , A n A_1,A_2,⋯,A_n A1,A2,⋯,An 是一个由 n 个自然数（非负整数）组成的数组。我们称其中 Ai,⋯,Aj 是一个非零段，当且仅当以下条件同时满足：
下面展示了几个简单的例子：
现在我们可以对数组 A 进行如下操作：任选一个正整数 p，然后将 A 中所有小于 p 的数都变为 0。试选取一个合适的 p，使得数组 A 中的非零段个数达到最大。若输入的 A 所含非零段数已达最大值，可取 p=1，即不对 A 做任何修改。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 n。
输入的第二行包含 n 个用空格分隔的自然数 A 1 , A 2 , ⋯ , A n A_1,A_2,⋯,A_n A1,A2,⋯,An。
输出格式
输出到标准输出。
仅输出一个整数，表示对数组 A 进行操作后，其非零段个数能达到的最大值。
样例1输入
11
3 1 2 0 0 2 0 4 5 0 2
样例1输出
5
样例1解释
p=2 时，A=[3,0,2,0,0,2,0,4,5,0,2]，5 个非零段依次为 [3]、[2]、[2]、[4,5] 和 [2]；此时非零段个数达到最大。
样例2输入
14
5 1 20 10 10 10 10 15 10 20 1 5 10 15
样例2输出
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输入
3
1 0 0
样例3输出
1
样例3解释
p=1 时，A=[1,0,0]，此时仅有 1 个非零段 [1]，非零段个数达到最大。
样例4输入
3
0 0 0
样例4输出
0
样例4解释
无论 p 取何值，A 都不含有非零段，故非零段个数至多为 0。
子任务
70% 的测试数据满足 n ≤ 1000 n≤1000 n≤1000；
全部的测试数据满足 n ≤ 5 × 1 0 5 n≤5×10^5 n≤5×105，且数组 A 中的每一个数均不超过 1 0 4 10^4 104。
已知：
(1) 非零段：数组中连续的不为0的一段数字(可以是单个数)
(2) 从A中选取p，将p中小于它的数都变为0，则A中的非零段个数会发生变化
求：A中非零段个数能达到的最大值
我们容易想到，对A中的值逐个选取成为p，再按要求对A中的数进行置0操作，每次完成后统计一下非零段个数，最后就可以得到最大值了。
所以我们先将统计非零段个数和根据p值置0的操作封装成单独的函数：
//求出数组的非零段个数
int count(int n) {
int k = 0;
if(a[0]!=0) k++;
for(int i=1; i<n; i++) {
if(a[i-1] != 0) continue;
else {
if(a[i] != 0) k++;
}
}
return k;
}
在这里为了方便计算，我将p值直接选取为A中的数组值，对小于等于p的数全部置0。
//将数组内小于等于p的数全部变为0
void change(int p, int n) {
for(int i=0; i<n; i++) {
if(a[i]<=p) a[i]=0;
}
}
但如果仅是通过遍历A来选取p值，不仅需要考虑数值重复出现的问题，并且每次都需要重新根据A的数据重新建立一个数组再置0再统计非零段个数。这样来实现一定会超时，并且代码撰写也很复杂。
进一步想，我们在置0时是将小于p的数都置0，如果我们选取p时是从小到大选取，那么每一次置0的过程就可以直接在上一次的基础上执行，可以节省时间。
因此，我们只要事先知道A中出现的数字从小到大有哪些就可以，这个可以用STL中的set容器来实现，在我们输入A数组的时候同时将数据插入set，内部会自动去重并排序。
根据以上的思路，我们来进行代码的实现。（虽然也只有70分，但思路没啥问题）
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
int a[500010];
//求出数组的非零段个数
int count(int n) {
int k = 0;
if(a[0]!=0) k++;
for(int i=1; i<n; i++) {
if(a[i-1] != 0) continue;
else {
if(a[i] != 0) k++;
}
}
return k;
}
//将数组内小于等于p的数全部变为0
void change(int p, int n) {
for(int i=0; i<n; i++) {
if(a[i]<=p) a[i]=0;
}
}
int main() {
int n;
set<int> setA;
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%d", &a[i]);
setA.insert(a[i]);
}
int maxNum = count(n); //非零段个数的最大值
//从小到大对p取值，并将数组a内小于等于p的数都变为0，再计算非零段个数
set<int>::iterator it = setA.begin();
while(it != setA.end()) {
change(*it, n);
int num = count(n);
if(num>maxNum) maxNum = num;
it++;
}
printf("%d", maxNum);
return 0;
}
代码只有70分，运行超时，说明循环执行次数太多，需要优化。
分析上述解法的运行过程，思路方向是正确的，那么就应该对反复运行的循环语句优化，看看能不能减少一些运行次数。
外层循环对p取值是没法再减少的，因为要得出非零段最大值肯定要对p所有情况进行计算（也有可能有更好的方法但是我想不到了）
再看内层循环，每次选取p之后都要从头到尾遍历两次——置0和统计非零段，应该有省时的方法。
对于非零段的计算，我们是每次都从头到尾重新计算的，但其实再思考一下非零段的定义，其实我们不难发现：要让非零段增多其实就是将一个长非零段变成两个短的，即将中间的数变为0。这样一来，其实再置0操作的同时我们就可以计算出非零段个数是否有变化，即：如果当前位的前后及其自身都不为0，将当前位置0就会使非零段+1；同样的，如果当前位的前后都为0，自身不为0，那么将当前位置0就会使非零段-1。
对于置0的操作，我们每一次都是从头到尾遍历A，找到符合条件的值置0来实现的。对此，我们可以用空间换时间，提前将每个数字出现的位置索引存储下来，在置0时就无需再去遍历寻找。 在这里我用STL中的vector容器来实现，定义一个vector类型的数组来存储每个数字出现的位置索引(类似于散列表的思想)。
vector<int> pos[10001];
//在输入的同时存储所在位置
for(int i=1; i<=n; i++) {
scanf("%d", &a[i]);
setA.insert(a[i]);
pos[a[i]].push_back(i); //存放当前数所在的位置索引
}
注意，这里的数组不能定义的太大，题目中提示数组 A 中的每一个数均不超过 1 0 4 10^4 104，所以我们将大小定为10001即可，太大会导致运行错误。
下面是最终具体的代码实现：
（在这里我将数组A的头和尾都补一个0，这样可以方便统计非零段，省略的头尾的特殊判断处理）
#include<cstdio>
#include<cmath>
#include<set>
#include<vector>
using namespace std;
int a[500010];
vector<int> pos[10001]; //存放每个数对应在数组中的索引
//求出数组的非零段个数
int count(int n) {
int k = 0;
//由0到非0时，非零段个数+1
for(int i=1; i<=n; i++) {
if(a[i-1]==0 && a[i]>0) k++;
}
return k;
}
int main() {
int n;
set<int> setA; //存放数组中出现过的数
scanf("%d", &n);
a[0] = a[n+1] = 0; //头尾补0，省去对头尾进行特殊判断
for(int i=1; i<=n; i++) {
scanf("%d", &a[i]);
setA.insert(a[i]);
pos[a[i]].push_back(i); //存放当前数所在的位置索引
}
int maxNum, temp; //非零段个数的最大值和当前值
maxNum = temp = count(n);
//从小到大对p取值：
set<int>::iterator iterator = setA.begin();
if(*iterator == 0) iterator++;
while(iterator != setA.end()) {
int p = *iterator;
for(vector<int>::iterator it=pos[p].begin(); it!=pos[p].end(); it++) {
int index = *it; //取出位置索引
a[index] = 0; //将该位置0
if( (a[index-1]>0) && (a[index+1]>0) ) temp++; //前后两个数都不为0时，非零段+1
if( (a[index-1]==0) && (a[index+1]==0) ) temp--; //前后两个数都为0时，非零段-1
}
if(temp > maxNum) maxNum = temp;
iterator++;
}
printf("%d", maxNum);
return 0;
}
