样例
输入样例:
3
4
1 2 2 4
8
11 12 1 2 13 14 3 4
4
7 6 5 4
输出样例:
4
2
1
算法1
(暴力枚举) $O(nlogn)$
分区间,如果不是非递减(遍历一次就可以知道),则删去一半,找两边最大值(递归)。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int a[N];
int dfs(int l,int r){
if(l>=r) return 1;
bool flag=true;//标识位
for(int i=l;i<r;i++){
if(a[i]>a[i+1])
{
flag=false;
break;
}
}
if(flag) return r-l+1;
int mid=l+r>>1;
return max(dfs(l,mid),dfs(mid+1,r));
}
int main()
{
int t;
scanf("%d", &t);
while (t -- ){
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{scanf("%d",&a[i]);
}
int res=dfs(1,n);
printf("%d\n",res);
}
return 0;
}