CCFCSP试题编号：202109-2试题名称：非零段划分
用差分法
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 500000;
const int M = 10000;
int a[N + 2 ]= { 0 };
int d[M + 1] = { 0 };
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> 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);
}
cout << ans << endl;
return 0;
}