AcWing 4489. 最长子序列
原题链接
中等
作者:
曦薇
,
2022-07-02 20:39:09
,
所有人可见
,
阅读 184
思路
- 因为数组本身有序,如果 $a_{j+1}$ 和 $a_j$ 不满足条件,那么 $a_{j+1}$ 更不可能和 $a_j$ 之前的数满足条件,所以从前往后遍历记录满足条件的最大长度即可。
- 时间复杂度为 $O(n)$ ,空间复杂度为 $O(n)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int num[N];
int main(void){
int n;
int ans=1,i,cnt;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&num[i]);
}
cnt=1;
for(i=2;i<=n;i++){
if(num[i]<=num[i-1]*2){
cnt++;
}else{
cnt=1;
}
ans=max(ans,cnt);
}
cout<<ans<<endl;
return 0;
}