题解 | 最长不下降子序列

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int a[]=new int[n+1];
		for (int i = 1; i <= n; i++) {
			a[i]=scanner.nextInt();
		}
		int dp[]=new int[n+5];//dp[i]表示以i结尾的序列，其中最长不降子序列的长度
		Arrays.fill(dp, 1);//初始化dp数组，每一个元素都赋值为1
		int max=1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j < i; j++) {
				if(a[j]<=a[i])dp[i]=Math.max(dp[i], dp[j]+1);
			}
			if(dp[i]>max)max=dp[i];
		}
		System.out.println(max);

	}

}

一定要记住，最后输出的是max而不是dpp[n]