[C++知识库]Acwing 消灭数组 3802

Acwing 3802 消灭数组 难度级别【简单】
题目描述
给定一个长度为 n 的数组，如果它不是非降序的，那么就将它的前半部分或后半部分消灭。

不断重复这个消灭一半数组的过程，直至数组变为升序为止。

请问，得以幸存的数组的最大可能长度是多少？

输入样例
3
4
1 2 2 4
8
11 12 1 2 13 14 3 4
4
7 6 5 4
输出样例
4
2
1

分析
1.注意题目中最大长度，即消除两边后都需计算，因此转化为两个子问题使用递归求两边求较大值
2.二分法注意左右边界，中间取left+(right-left)/2

C++ 代码

#include<iostream>
using namespace std;
bool nonDe(int data[],int left,int right) {
    for (int i = left; i < right; i++) {
        for (int j = i + 1; j <=right; j++) {
            if (data[j] < data[i])
                return 0;
        }
    }
    return 1;
}
int calMax(int data[],int left,int right){
        if (nonDe(data, left,right) == 1)
            return right-left+1;
        else {
            return max(calMax(data, left, left+(right-left) / 2), calMax(data, left+(right -left)/ 2 + 1, right));
        }
}
int main()
{
    int T;
    int n[10], a[10][16], maxlength[10];
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> n[i];
        for (int j = 0; j < n[i]; j++)
            cin >> a[i][j];
        if (nonDe(a[i], 0,n[i]-1) == 0)
            maxlength[i] = calMax(a[i], 0,n[i]-1);
        else
            maxlength[i] = n[i];
    }
    for (int i = 0; i < T; i++)
        cout << maxlength[i] << endl;
    return 0;
    system("pause");
}