题解 | 最长不下降子序列

import java.util.Scanner;
import java.util.Arrays;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a=in.nextInt();
        int s[]=new int[a];
        int dp[] =new int[a];
        int flag=1;
         int i ,j,ml=1;
       
        for(i=0;i<a;i++){
            s[i]=in.nextInt();
        }
        Arrays.fill(dp,1);
        for(i=0;i<s.length-1;i++){
            for(j=i+1;j<s.length;j++){
                if(s[i]<=s[j]){
                    //dp[j]=dp[i]+1;
                    dp[j]=Math.max(dp[i]+1,dp[j]);
                    ml=Math.max(ml,dp[j]);
                }
            }
        }
        System.out.print(ml);
    }
}

状态转移方程： dp[j]=Math.max(dp[i]+1,dp[j]);

思路：

观察示例一中的子序列，第i个数字的最长序列由i-1个数字的最长序列获得

得到一个假的状态方程：dp[j]=dp[i]+1;

去循环遍历填表：

 for(i=0;i<s.length-1;i++){
            for(j=i+1;j<s.length;j++){
                if(s[i]<=s[j]){
                    dp[j]=dp[i]+1;
                }
            }
        }

可以对一些实例，

发现一个新的问题，在某个实例中，条件s[i]<=s[j]满足，但是dp[j]在其他循环中记录的最长序列，比当前要记录的最长序列dp[i]+1大，所以dp[j]被覆盖成最小了，

所以要在dp[i]+1和dp[j]中取最大值来记录

新的状态转移方程： dp[j]=Math.max(dp[i]+1,dp[j]);

但是还是不能全对

以下面为例；

10

298442 20400 774061 202518 319008 514069 740053 470905 431457 66193

dp数组中内容是

121222221

22222222

2222222

333332

44442

5442

442

42

2

发现整个序列的最大序列记录值不在最后，所以需要一个ml记录最大值输出