AcWing 895. 最长上升子序列
原题链接
简单
作者:
hhu-菜菜
,
2021-05-19 19:10:29
,
所有人可见
,
阅读 200
import java.util.Scanner;
class Main{
static final int N = 1010;
static int n;
static int[] a = new int[N];
static int[] dp = new int[N];
static int[] dp = new int[N];
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
n = reader.nextInt();
for(int i = 1;i <= n;i++){
a[i] = reader.nextInt();
}
reader.close();
for(int i = 1;i <= n;i++){
dp[i] = 1;//只有a[i]一个数
for(int j = 1;j < i;j++){
if(a[j] < a[i]){
if(dp[i] < dp[j]+1){
dp[i] = d[j]+1;
g[i] = j;
}
}
}
}
int k = 1;
for(int i = 1;i <= n;i++){
if(dp[k] < dp[i]){
k = i;
}
}
System.out.println(dp[i]);
for(int i = 0,len = dp[k];i < len;i++){
System.out.print(a[k]);
k = g[k];
}
}
}