最长递增子序列

https://www.nowcoder.com/profile/803722233/codeBookDetail?submissionId=136300366

最长递增子序列

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
自己写的，动态规划，超时

https://www.nowcoder.com/profile/803722233/codeBookDetail?submissionId=136309612

二分查找

https://www.nowcoder.com/profile/803722233/codeBookDetail?submissionId=136309756

思路

等价问题：
[1 ~ k] 所有整数构成的序列，找出长度为n，和为x的子序列 如果K在子序列中，则在[1 ~ k-1]在中长度为n-1的，和为x-k的子序列； 否则，在[1 ~ k-1]在中长度为n的，和为x的子序列；

答案(动态规划)

1、定义辅助数组

int[] dp = new int[len];//dp[i]表示i之前包括i的最⻓上升⼦序列。

2、初始化

每⼀个i，对应的dp[i]（即最⻓上升⼦序列）起始⼤⼩⾄少都是是1.

3、递推关系（状态转移⽅程）

• 位置i的最⻓升序⼦序列等于j从0到i-1各个位置的最⻓升序⼦序列 + 1 的最⼤值。
• 所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
• 注意这⾥不是要dp[i] 与 dp[j] + 1进⾏⽐较，⽽是我们要取dp[j] + 1的最⼤值。

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        // write code here
        if(n <= 1){
            return n;
        }
        int[] dp = new int[n];
        int res = 0;
        for(int i=0;i<n;i++){
            dp[i] = 1;//初始化
            for(int j=0;j<i;j++){
                if(A[i] > A[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if(dp[i] > res){
                res = dp[i];// 取最⻓的⼦序列
            }
        }
        System.out.println(res);
        return res;
    }
}