最长递归子序列问题

题目

递增子序列是指：从原序列中按顺序挑选出某些元素组成一个新序列，并且该新序列中的 任意一个元素均大于该元素之前的所有元素。例如，对于序列 < 5, 24, 8, 17, 12, 45 >，该序列的 两个递增子序列为 < 5, 8, 12, 45 > 和 < 5, 8, 17, 45 >，并且可以验证它们也是原序列最长的递增 子序列。请设计算法来求出一个包含 n 个元素的序列 A =< a1, a2, · · · , an > 中的最长递增子序 列，并分析该算法的时间复杂度。

解题

这是一个动态规划问题
首先，我们设立dp数组，其中第i个数表示以数组第i个数结尾的最长子序列的大小。
其次，进行状态初始化，再进行状态转移，最后返回dp[n-1].
状态转移方程：
分析可知，时间复杂度为O(n^2)
代码如下

public int maxChildSequence(int[] a) {
    int n = a.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }
    return dp[n - 1];
}