每日算法 — 使用java实现最长递增子序列：动态规划与二分查找优化

最长递增子序列（Longest Increasing Subsequence，简称LIS）是动态规划领域的经典问题。给定一个整数序列，求其中最长的严格递增子序列的长度。该问题在生物信息学（基因序列比对）、数据压缩、卡牌游戏策略分析等领域都有广泛应用。

问题定义与示例

给定数组 nums = [10, 9, 2, 5, 3, 7, 101, 18]，其最长递增子序列是 [2, 3, 7, 101]，长度为4。注意子序列不要求连续，但要求相对顺序不变。

方法一：动态规划解法（O(n²)）

核心思路

定义 dp[i] 为以第 i 个元素结尾的最长递增子序列的长度。对于每个位置 i，我们遍历所有前面的位置 j（j < i），如果 nums[j] < nums[i]，则 dp[i] 可以从 dp[j] 转移而来。

状态转移方程：

dp[i] = max(dp[j] + 1)  其中 j < i 且 nums[j] < nums[i]

初始状态：dp[i] = 1（每个元素自身构成长度为1的递增子序列）

Java实现

public class LISDynamicProgramming {

    /**
     * 动态规划解法，时间复杂度O(n²)，空间复杂度O(n)
     * @param nums 输入数组
     * @return 最长递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        // dp[i]表示以nums[i]结尾的最长递增子序列长度
        int[] dp = new int[n];

        // 初始化：每个元素自身构成长度为1的LIS
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        int maxLength = 1;

        // 遍历每个位置，计算以该位置结尾的LIS长度
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 如果nums[j] < nums[i]，可以扩展递增子序列
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新全局最大值
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }

    /**
     * 扩展：不仅返回长度，还返回具体的最长递增子序列
     */
    public int[] getLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n]; // 记录前驱节点，用于回溯路径

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            prev[i] = -1;
        }

        int maxLength = 1;
        int maxIndex = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j; // 记录前驱
                }
            }
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                maxIndex = i;
            }
        }

        // 回溯构建子序列
        int[] result = new int[maxLength];
        int idx = maxLength - 1;
        while (maxIndex != -1) {
            result[idx--] = nums[maxIndex];
            maxIndex = prev[maxIndex];
        }

        return result;
    }

    public static void main(String[] args) {
        LISDynamicProgramming solution = new LISDynamicProgramming();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};

        System.out.println("输入数组: " + java.util.Arrays.toString(nums));
        System.out.println("LIS长度: " + solution.lengthOfLIS(nums));
        System.out.println("LIS序列: " + java.util.Arrays.toString(solution.getLIS(nums)));
    }
}

方法二：二分查找优化（O(n log n)）

核心思路

维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。遍历数组时，用二分查找确定当前元素在 tails 中的位置：

• 如果当前元素大于 tails 中所有元素，则追加到末尾，LIS长度增加
• 否则，用当前元素替换 tails 中第一个大于等于它的元素，保持数组有序

这个技巧利用了贪心思想：让相同长度的递增子序列以尽可能小的元素结尾，更有利于后续扩展。

Java实现

public class LISBinarySearch {

    /**
     * 二分查找优化解法，时间复杂度O(n log n)，空间复杂度O(n)
     * @param nums 输入数组
     * @return 最长递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        // tails[i]表示长度为i+1的递增子序列的最小末尾元素
        int[] tails = new int[n];
        int size = 0; // 当前LIS的长度

        for (int num : nums) {
            // 二分查找：找到tails中第一个>=num的位置
            int left = 0, right = size;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            // left就是插入位置
            tails[left] = num;

            // 如果插入位置在末尾，说明LIS长度增加了
            if (left == size) {
                size++;
            }
        }

        return size;
    }

    /**
     * 扩展：返回具体的最长递增子序列（ patience sorting 思想）
     */
    public int[] getLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] tails = new int[n];
        int[] tailIndices = new int[n]; // 记录每个长度对应的元素在原数组中的索引
        int[] prev = new int[n]; // 前驱索引

        int size = 0;

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int left = 0, right = size;

            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            tails[left] = num;
            tailIndices[left] = i;

            // 记录前驱
            if (left > 0) {
                prev[i] = tailIndices[left - 1];
            } else {
                prev[i] = -1;
            }

            if (left == size) {
                size++;
            }
        }

        // 回溯构建结果
        int[] result = new int[size];
        int idx = tailIndices[size - 1];
        for (int i = size - 1; i >= 0; i--) {
            result[i] = nums[idx];
            idx = prev[idx];
        }

        return result;
    }

    public static void main(String[] args) {
        LISBinarySearch solution = new LISBinarySearch();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};

        System.out.println("输入数组: " + java.util.Arrays.toString(nums));
        System.out.println("LIS长度: " + solution.lengthOfLIS(nums));
        System.out.println("LIS序列: " + java.util.Arrays.toString(solution.getLIS(nums)));
    }
}

两种方法的对比分析

复杂度分析

动态规划解法：
– 时间复杂度：O(n²)，双重循环遍历
– 空间复杂度：O(n)，dp数组

二分优化解法：
– 时间复杂度：O(n log n)，每次二分查找耗时O(log n)
– 空间复杂度：O(n)，tails数组

变种问题与拓展

1. 最长递减子序列：将比较符号取反，或反转数值符号后求LIS
2. 最长非递减子序列：将 nums[j] < nums[i] 改为 nums[j] <= nums[i]
3. 二维LIS：如俄罗斯套娃信封问题，先按一维排序，再在另一维上求LIS
4. 最长公共子序列（LCS）：可通过LIS技巧在特定条件下优化

总结

最长递增子序列问题是理解动态规划与贪心策略结合的绝佳案例。动态规划解法思路清晰，适合理解问题本质；二分优化解法展示了如何将时间复杂度降低一个数量级，是算法竞赛和工程实践中的常用技巧。掌握这两种方法，能够应对绝大多数LIS及其变种问题。