手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

选择子序列

时间:2021/8/3 12:27:56|来源:|点击: 次

题目链接
长度为N的整数数组A,所有的数均不相同,假设下标从0开始。找到一个最长的数组B,B数组的长度为K,数值范围是0 - N - 1,记录的是A数组的下标。满足A[B[0]] > A[B[1]] > A[B[2]] >…A[B[K]],并且对任意连续的两项B[i]及B[i + 1],满足min(B[i],B[i + 1]) < j < max(B[i],B[i + 1]) 均有A[j] < A[B[i + 1]] ,求最大的K。例如:9, 10, 2, -1, 3, -5, 0, -3, 1, 12, 5, 8, -2, 6, 4。可以选出:12, 10, 3, 1, 0, -3。对应的下标为:9, 1, 4, 8, 6, 7(就是B数组),输出6。
输入
第1行:一个数N,表示A数组的长度。(1 <= N <= 50000)
第2 - N + 1行:每行1个数对应A数组的元素Ai(0 < Ai < 10^9)
输出
输出B数组最长的长度K。
输入样例
15
9
10
2
-1
3
-5
0
-3
1
12
5
8
-2
6
4
输出样例
6

#include<bits/stdc++.h>
using namespace std;
int n,a[50100];
int dfs(int l,int r){
    if(l>r)
    return 0;
    if(l==r)
    return 1;
    int central=0,position=0;
    for(int i=l;i<=r;i++){
        if(a[i]>central){
            central=a[i];
            position=i;
        }
    }
    return max(dfs(l,position-1),dfs(position+1,r))+1;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int ans=dfs(0,n-1);
    cout<<ans<<endl;
    return 0;
}

Copyright © 2002-2019 某某自媒体运营 版权所有