CCF分类，CCF202109-2 非零段划分

主要用到差分法

借用岛屿情况来分析这个题。考虑p足够大的情况，所有的数都被海水淹没了，只有0个岛屿。然后，海平面逐渐下降，岛屿数量出现变化。每当一个凸峰出现，岛屿数就会多一个；每当一个凹谷出现，原本相邻的两个岛屿就被这个凹谷连在一起了，岛屿数减少一个。使用数组cnt[]，cnt[i] 表示海平面下降到i时，岛屿数量的变化。
　　差分法是最简洁的解题程序。数组元素d[i]中存储该元素被替换为0时，划分数变化的差分值。最大值则只需要从其前缀和（程序中实际为后缀和）中找出最大值就是所要的结果。
　　程序代码中，STL算法函数unique()用来去除相邻重复的元素。
　　语句“a[0] = a[n + 1] = 0;”用来设置边界值，起辅助计算作用，可以简化程序代码。

 解题代码：

/* CCF202109-2 非零段划分 */
#include <bits/stdc++.h>
using namespace std;
const int N = 500000;
const int M = 10000;
int a[N + 2], d[M + 1];
int main()
{int n;scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);a[0] = a[n + 1] = 0;n = unique(a, a + n + 2) - a - 1;memset(d, 0, sizeof d);for (int i = 1; i < n; i++)if (a[i - 1] < a[i] && a[i] > a[i + 1]) d[a[i]]++;else if (a[i - 1] > a[i] && a[i] <a[i + 1]) d[a[i]]--;int ans = 0, sum = 0;   // 差分前缀和即为答案for (int i = M; i >= 1; i--)sum += d[i], ans = max(ans, sum);printf("%d\n", ans);return 0;
}