最长上升子序列问题 

有一个长为n的数列a0,a1,...,a(n-1)。请求出这个序列中最长的上升子序列的长度。
上升子序列指的是对于任意的i j都满足ai aj的子序列。

1≤n≤1000
0≤ai≤1000000

 输入 

n=5
a={4,2,3,1,5}

 输出 

3（注：2，3，5）

分析

首先用暴力解法 O(n^2) 遍历每一种可能性 可以很轻松的得到结果
接着 使用dp法 但是比较晦涩

package BlueCup.Eight_DP_greed; import java.util.Scanner; import static java.lang.Math.max; public class 最长上升子序列 { public static void main(String[] args) {
        Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) {
            a[i] = cin.nextInt();
        }
        System.out.println(f(a, n));
        System.out.println(dp(a, n));
        System.out.println(dp01(a, n));

    } /**
     * dp[i] 长度为i的L  O(nlgn)
     * IS
     * @param a
     * @param n
     * @return */ private static int dp01(int a[], int n) { int[] dp = new int[n + 1]; int p;//记录dp更新的最后位置 dp[p = 1] = a[0];//长度为1的最长递增子序列，初始化为第一个元素 for (int i = 1; i < a.length; i++) { if (a[i] > dp[p])//新元素和dp的关系 如果遇到比i大的数 那就 存进去 并指针后移 dp[p++ + 1] = a[i];//递增子序列长度增加 else {//递增子序列长度 不 增加 //扫描dp 替换第一个比arr[i]大的dp for (int j = 0; j <= p; j++) { if (dp[j] > dp[i])// dp[j] = a[i];
                }
            }
        } return p;
    } /**
     * dp 递推 逐步解决
     * O(n^2)pd[i] 是以i结尾的 序列
     * j是待比较 i是比较的目标
     *
     * @param a
     * @param n
     * @return */ private static int dp(int[] a, int n) { int[] dp = new int[n];
        dp[0] = 1; for (int i = 1; i < n; i++) { int cnt = 1; for (int j = i - 1; j >= 0; j--) { if (a[i] > a[j])
                    cnt = max(cnt, dp[j] + 1);//所有dp表中最大的~ }
            dp[i] = cnt;
        } int ans = -1; for (int i : dp) ans = max(ans, i);//最后遍历一遍dp[i] return ans;
    } /**
     * 暴力解法 o(n^2)
     *
     * @param a
     * @param n
     * @return */ private static int f(int[] a, int n) { int maxCnt = 0; for (int i = 0; i < n; i++) { int cnt = 1;//从1 开始 最短就是1 int p = i;//记录被大于的数值索引 for (int j = i + 1; j < n; j++) { if (a[j] > a[p]) {
                    cnt++;
                    p = j;
                }
            }
            maxCnt = max(maxCnt, cnt);
        } return maxCnt;
    }
}