记忆化搜索(Java版本)
import java.util.*;
//状态:以 i 为起点的单调递增的子序列
//属性:Max
//状态转移方程:f[i] = Max(f[i],f[j] + 1), 下标j需要满足a[i] < a[j]
public class Main{
static int n = 0;
static int[] arr = new int[1010];
static int[] f = new int[10010];
//dp方法表示求以 x 下标开头的递增子序列长度最长
public static int dfs(int x){
//记忆化搜索,已经计算过的不用再次计算
if(f[x] != 1){
return f[x];
}
//从x点往后扫即可
for(int i = x+1;i <= n;i++){
if(arr[i] > arr[x]){
f[x] = Math.max(f[x],dfs(i) + 1);
}
}
return f[x];
}
public static void main(String[] args){
int max = 0;
Scanner in = new Scanner(System.in);
n = in.nextInt();
for(int i = 1;i <= n;i++){
arr[i] = in.nextInt();
}
for(int i = 1;i <= n;i++){
//初始化为 1,因为最短的单调递增的子序列长度是 1
f[i] = 1;
}
for(int i = 1;i <= n;i++){
dfs(i);
}
for(int i=1;i<=n;i++){
max = max < f[i] ? f[i] : max;
}
System.out.println(max);
}
}