题解 | #Redraiment的走法#

#include<stdio.h>
#include<stdlib.h>
int max = 1;
void solu(int arr[],int step,int value,int idx,int n){
    int f = 0;
    for(int i=idx;i<n;i++){
        if(arr[i]>value){
            solu(arr,step+1,arr[i],i+1,n);
            f = 1;
        }
    }
    if(f==0){
        if(step>max)
            max = step;
    }
}

int main(){
    int n;
    scanf("%d",&n);
    int*arr = (int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    // 方法1 dfs  - 300ms ---
//     int step = 0;
//     int value = 0;
//     int idx = 0;
//     solu(arr,step,value,idx,n);
//     printf("%d",max);
//     free(arr);
    
    // 方法2 类似  合唱队   从左往右的最大升序
    int*lmax = (int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++) lmax[i] = 1;
    int max = 1;
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(arr[j]<arr[i] && lmax[j]==lmax[i]){ //在j左侧有都有相同的序列
                lmax[i] = lmax[j]+1;
                if(lmax[i]>max)
                    max  = lmax[i];
            }
        }
    }
    printf("%d",max);
    
}