题目
C++代码
// 202109-2 非零段划分
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 500010;
const int M = 10010;
int a[N], d[M]; // d[i] 为差分数组
bool c[N];
int n, ans, sum;
int main() {
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; // unique去除相邻两个重复元素
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]]--;
}
}
for (int i = 10000; i >= 1; i--) {
sum += d[i];
ans = max(ans, sum);
}
printf("%d\n", ans);
return 0;
}
标签:int,sum,非零段,202109,ans,include,CSP
From: https://www.cnblogs.com/catting123/p/17701357.html