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

问题描述

给定一个整数数组 nums，找到其中最长的严格递增子序列的长度。子序列不要求连续，但要求相对顺序不变。

示例：nums = [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列为 [2, 3, 7, 101]，长度为 4。

该问题在生物信息学序列比对、股票趋势分析、数据压缩等领域有重要应用。

解法一：基础动态规划 O(n²)

设 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。

public class LISDynamicProgramming {

    // O(n²) 动态规划
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] dp = new int[n];
        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 每个元素自身构成长度为1的LIS
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    // 还原具体的LIS序列
    public static int[] getLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n]; // 记录前驱节点
        int maxLen = 1, maxIdx = 0;

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            prev[i] = -1;
            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] > maxLen) {
                maxLen = dp[i];
                maxIdx = i;
            }
        }

        // 回溯构建序列
        int[] lis = new int[maxLen];
        int k = maxLen - 1;
        for (int i = maxIdx; i != -1; i = prev[i]) {
            lis[k--] = nums[i];
        }
        return lis;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("LIS长度: " + lengthOfLIS(nums));
        System.out.println("LIS序列: " + java.util.Arrays.toString(getLIS(nums)));
    }
}

解法二：Patience Sorting 二分优化 O(n log n)

将数组元素像玩纸牌一样按规则放置到堆上：每个元素放到最左边堆顶大于等于它的堆上，否则新建一堆。堆的数量即为 LIS 长度。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LISBinarySearch {

    // O(n log n) 二分优化，tails[i] 表示长度为 i+1 的递增子序列的最小末尾值
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        List<Integer> tails = new ArrayList<>();
        for (int num : nums) {
            int idx = Collections.binarySearch(tails, num);
            if (idx < 0) idx = -(idx + 1); // 未找到，取插入位置

            if (idx == tails.size()) {
                tails.add(num); // 延长LIS
            } else {
                tails.set(idx, num); // 替换，保持更小末尾
            }
        }
        return tails.size();
    }

    // 更底层的二分实现，不依赖Collections
    public static int lengthOfLISRaw(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] tails = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            int lo = 0, hi = size;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < num) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            tails[lo] = num;
            if (lo == size) size++;
        }
        return size;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("LIS长度(List): " + lengthOfLIS(nums));
        System.out.println("LIS长度(Raw): " + lengthOfLISRaw(nums));
    }
}

核心思想解析

二分优化为何正确？tails 数组维护了一个贪心性质：对于每个长度，记录最小的末尾元素。当遇到新元素时，如果能接在某个长度后面就接，否则用它替换某个更大的末尾，为后续元素创造更多机会。

这种思想被称为 Patience Sorting，与纸牌游戏 patience 的玩法一致。

复杂度对比

扩展思考

若要求最长递减子序列，只需将所有比较符号取反，或先对数组取负数。若要求最长连续递增子序列（子数组），则问题简化为线性扫描。

总结

LIS 问题是动态规划与贪心结合的经典范例。基础 DP 帮助我们理解问题结构，而二分优化则展示了算法设计中”维护最优子结构”的精妙之处。