28. 最长上升子序列：在一个给定的数组中找到最长的上升子序列的长度

PangHu大约 3 分钟

寻找最长上升子序列（LIS, Longest Increasing Subsequence）的长度是一个经典的动态规划问题。下面介绍两种常见的解法：动态规划（DP）方法和动态规划结合二分查找的方法。

1. 方法一：动态规划（DP）

1.1 算法思路

使用一个数组 dp，其中 dp[i] 表示以元素 nums[i] 结尾的最长上升子序列的长度。
初始时，每个位置的最长上升子序列长度都至少为 1，因此 dp[i] = 1。
对于每个 i，检查在它之前的所有元素 j（j < i），如果 nums[i] > nums[j]，则 dp[i] 可以更新为 dp[i] = max(dp[i], dp[j] + 1)。
最后，整个数组中最长的上升子序列长度就是 dp 数组中的最大值。

1.2 代码实现

public class LongestIncreasingSubsequence {

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] dp = new int[n];
        int maxLength = 1;

        // 初始化 dp 数组，每个位置的最长上升子序列长度至少为 1
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        // 填充 dp 数组
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence solution = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = solution.lengthOfLIS(nums);
        System.out.println("The length of the longest increasing subsequence is: " + result);
    }
}

1.3 复杂度分析

时间复杂度：O(n^2)，其中 n 是数组的长度。双重循环遍历所有的元素对。
空间复杂度：O(n)，需要一个长度为 n 的 dp 数组来存储最长上升子序列的长度。

2. 方法二：动态规划结合二分查找

2.1 算法思路

通过结合二分查找，可以将时间复杂度优化到 O(n log n)：

使用一个辅助数组 tail，其中 tail[i] 存储长度为 i+1 的最长上升子序列的最后一个元素的最小可能值。
遍历原数组，对每个元素 num：
- 使用二分查找确定 num 应该插入 tail 数组的位置 pos。
- 如果 num 大于 tail 中所有元素，将其添加到 tail 的末尾。
- 否则，更新 tail[pos] 为 num。
最终 tail 数组的长度就是最长上升子序列的长度。

2.2 代码实现

import java.util.Arrays;

public class LongestIncreasingSubsequence {

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] tail = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            int i = 0, j = size;
            while (i != j) {
                int mid = (i + j) / 2;
                if (tail[mid] < num) {
                    i = mid + 1;
                } else {
                    j = mid;
                }
            }
            tail[i] = num;
            if (i == size) size++;
        }

        return size;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence solution = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = solution.lengthOfLIS(nums);
        System.out.println("The length of the longest increasing subsequence is: " + result);
    }
}

2.3 复杂度分析

时间复杂度：O(n log n)，其中 n 是数组的长度。每个元素的二分查找时间复杂度为 O(log n)。
空间复杂度：O(n)，需要一个长度为 n 的 tail 数组。

3. 例子解释

对于数组 {10, 9, 2, 5, 3, 7, 101, 18}，最长的上升子序列为 {2, 3, 7, 101}，其长度为 4。

4. 总结

动态规划法：简单易懂，适合初学者，但时间复杂度较高为 O(n^2)。
动态规划结合二分查找：时间复杂度优化到 O(n log n)，适合大规模数据的处理。

通过以上两种方法，你可以在不同的场景中选择适合的算法来求解最长上升子序列的问题。