链接:https://ac.nowcoder.com/acm/contest/558/E
来源:牛客网
小猫在研究序列。
小猫在研究单调性。
给定一个长度为N的序列a1,a2,…,aN,请你选出一个最长的区间[l,r](1≤l≤r≤N),满足al≤al+1≤…≤ar。
如果有多个,请输出l最小的。
思路:模拟
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int main() {
int T, n;
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (int i =1 ; i <= n; i++) {
cin >> a[i];
}
a[n + 1] = -1;
int L = 1, R = 1;
int cnt = 0;
int l = 1, r = 1;
int ans = 0;
for (int i = 1; i <= n + 1; i++) {
if (a[i] >= a[i - 1]) {
cnt++;
} else {
if (cnt > ans) {
ans = cnt;
l = L; r = i - 1;
R = i - 1;
}
L = i; R = i;
cnt = 1;
}
}
cout << l << " " << r << endl;
}
return 0;
}