如何实现最长上升子序列算法？

最长上升子序列(Longest Increasing Subsequence, LIS)问题是求一个序列中的最长上升子序列的长度。

我们可以使用动态规划实现LIS算法:

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int len = 0;

    for (int num : nums) {
        int i = Arrays.binarySearch(dp, 0, len, num);
        if (i < 0) i = -(i + 1);   // 若找不到大于等于num的数,i为第一个大于num的数的索引
        dp[i] = num;

        if (i == len) len++;      // 若num大于dp中的所有数,最长上升子序列长度加1
    }

    return len;
} 

算法流程:

1. 初始化dp数组和len。dp数组存储最长上升子序列,len为最长上升子序列的长度。
2. 遍历nums中的每个数num。使用二分查找在dp数组中找到第一个大于等于num的数所在位置i。
3. 如果找到,将dp[i]更新为num。否则,将num添加到dp的末尾,最长上升子序列长度len加1。
4. 重复步骤2和3,最终dp数组存储最长上升子序列,len为最长上升子序列的长度。
5. 返回len,得到最长上升子序列的长度。

时间复杂度 O(nlogn),空间复杂度 O(n)。

所以,最长上升子序列的关键是:

1. 定义dp数组存储最长上升子序列,len存储最长上升子序列的长度。
2. 对于每个数,使用二分查找找到dp中第一个大于等于它的数的位置,并更新dp[i]或者添加到dp的末尾。
3. 如果添加到末尾,最长上升子序列的长度len加1。
4. 重复上述步骤,最终dp数组为最长上升子序列,len为最长上升子序列的长度。