题解 | 最长不下降子序列

#include<stdio.h>
#include<stdlib.h>
int n;
int main(){
    scanf("%d",&n);
int *a=(int*)malloc((n+3)*sizeof(int));
int *dp=(int*)malloc((n+3)*sizeof(int));
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
dp[i]=0;
    }
dp[1]=1;
int max=dp[1];
int min=1;
 int found=0;
for(int i=2;i<=n;i++){
    found=0;
    min=1;
for(int j=i-1;j>=1;j--){
    if(a[j]<=a[i]){
if(min<dp[j]){
    min=dp[j];
}
found=1;
    }

}
if(found==1){
    dp[i]=min+1;
}else
if(found==0){
    dp[i]=1;
}
if(max<dp[i]){
    max=dp[i];
}
}
printf("%d",max);
}

依旧是把大问题拆分为小问题：这个思想类是上道题一样，将每个dp[i]都写出来，从小往大的来，同时你要意识到我到了i点，是要找前面比a[i]要小的，同时要其dp是最大的！按这个思路，就出来了，依旧是大问题变小问题