问题描述

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

样例输出

评测用例规模与规定

70% 的测试数据满足 n≤1000；

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

思路

首先，由题目可得，存在一个正整数p，使得数组A经过p的处理之后得到最多的非零段。我一开始的思路是，当经过p处理修改a[i]为0后，a[i-1]和a[i+1]都等于0时非零段减一，都不等于0时非零段加一。最后记下非零段最多的时候。如果不经过其他处理这样只可以过70%的数据。

这道题其实考的是对前缀和和差分数组的性质的理解。当a[i]>a[i-1]时，当p取到这两个数之间的值时，这里会出现一个非零段，也就是非零段加1，这就需要对一个范围都加上1，这就可以用到差分数组的性质，当我们要对一个范围[l,r]的数全体加上或减去某个值n时，我们只需要对它的差分数组diff[l]+n,diff[r+1]-n;然后再求前缀和得到的数组便是进行处理之后的数组。

（对前缀和还有差分数组一点都不了解的可以去看看这位大佬的博客ycloong’s blog）

参考代码

70分代码

public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	ArrayList<Integer> list = new ArrayList<Integer>();
	list.add(0);
	int n = scanner.nextInt();
	int sum = 0,maxs = 0;
	boolean f = false; 
	for(int i = 0;i < n;i ++) {
		int t = scanner.nextInt();
		list.add(t);
		if(t != 0) {
			if(!f) {
				sum ++;
				f = true;
			}
		}else {
			f = false;
		}
	}
	maxs =Math.max(maxs, sum);
	list.add(0);
	ArrayList<Integer> list2 = new ArrayList<Integer>();
	for (Integer in : list) {
		if (!list2.contains(in)) {
			list2.add(in);
		}
	}
	list2.sort(Comparator.naturalOrder());
	for(int i : list2) {
		for(int j = 1;j < n+1;j ++) {
			int k =list.get(j);
			if(k <= i && k != 0) {
				list.set(j, 0);
				int k1 = list.get(j-1),k2 = list.get(j+1);
				if(k1 == 0 && k2 == 0) {
					sum --;
				}
				else if(k1 != 0 && k2 != 0) {
					sum ++;
				}
			}
		}
		maxs = Math.max(maxs, sum);
	}
	System.out.println(maxs);
}

100分代码

static int N = 100000;
static int []dif = new int[N];
	public static void add(int l,int r) {
		dif[l]++;
		dif[r + 1]--;
	} //对差分数组进行一整段的加减
	public static void main(String[] args) {
		new _0902().run();
	}
	public void run() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int []a = new int[n+1];
		a[0] = 0; //数组最前面要放一个0，不然开始就会判断错误
		for(int i = 1;i < n+1;i ++) {
			a[i] = scanner.nextInt();
		}
		for (int i = 1; i < n+1; i++) {
	        if (a[i] > a[i-1]) {
	            add(a[i - 1] + 1, a[i]);
	        }
	    }
		int maxn = 0, pre = 0;
	    for (int p = 1; p < 1e4; p++) {
	        pre += dif[p];
	        maxn = Math.max(maxn, pre);
	    }
	    System.out.println(maxn);
	}