题目：

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000，
−10^9≤数列中的数≤10^9

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

 

DP分析：

代码：

import java.io.*;
import java.util.*;

class Main{
    static int N = 1010;
    static int[] w = new int[N];
    static int[] f = new int[N];
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine()); 
        String[] s = in.readLine().split(" ");
        for(int i=1;i<=n;i++){
                w[i] = Integer.parseInt(s[i-1]);
        }
        
        // DP
        for(int i=1;i<=n;i++){
            f[i] = 1; // 只有自身
            for(int j=1;j<i;j++){
                if(w[j]<w[i]) // 保证序列单调上升
                    f[i] = Math.max(f[i],f[j]+1);
            }
        }
        
        // 不一定f[n]就是最长的，因为f[n]必定包含w[n]这个数，最长上升子序列可能不包含w[n]
        int res = 0;
        for(int i=1;i<=n;i++) res = Math.max(res,f[i]);
        System.out.println(res);
    }
}

 PS：

本来想尝试单调栈的。发现比如  3 1 2 1 8 5 6 。栈会删去 2 ，存进 1。而最长上升子序列为 1 2 5 6。