题解 | 最长不下降子序列

1.动态规划

依旧先创建原始数组a[n]接收数据。

关键点：子序列的定义，我们是可以删除原数组的元素，也就是从这杜绝了线性dp的可能。

此时我们可以定义dp[],dp[ i ] 代表以a数组的第i个元素结尾的最大的序列长度。

因为a数组每个元素都可以视为单独的序列，即dp数组的初始化均为1。

import java.util.*;

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int a[] = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0;i<n;i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
        int dp[] = new int[n];
        int maxlen = 0;
        for(int i = 0;i<n;i++){
            dp[i] = 1;
            for(int j = 0;j<i;j++){
                if(a[j]<=a[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            maxlen = Math.max(maxlen,dp[i]);
        }
        System.out.println(maxlen);
    }
}

逻辑：初始化dp数组为1，然后建立一个小循环获取当前 i 之前的最大的dp[j]值(对应的a[j]应当小于等于此时的a[i])

关键(删除元素的逻辑的实现):每一次的更新的dp[i]其实都是遍历先前的最大dp[j](条件a[j]<=a[i]),而dp[j]是存储以当前a[j]结尾的最长的序列长度，所以对应的a[j]<=a[i]的话就可以参与比较，相反的如果a[j]>a[i]就自动将其排除