算法背景
最长上升子序列（Longest Increasing Subsequence，LIS）是动态规划的经典入门问题：给定一个整数序列，找出一个最长的子序列，使得子序列中的元素严格递增。LIS 及其变种在数据流分析、基因序列比对、卡牌游戏策略和机器学习中的序列建模等领域都有重要应用。
核心思想
- O(n²) 动态规划：
dp[i]表示以第 i 个元素结尾的最长上升子序列长度，状态转移为dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]。 - O(n log n) 优化：维护一个数组
tails，其中tails[k]表示长度为k+1的上升子序列的最小末尾元素。通过二分查找确定每个元素的插入位置，将时间复杂度优化到 O(n log n)。这一优化思路与 patience sorting（耐心排序）密切相关。
完整Java实现
import java.util.*;
public class LISFinder {
/**
* O(n^2) 动态规划解法，适合理解核心思想
*/
public static int lengthOfLIS_DP(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
Arrays.fill(dp, 1); // 每个元素自身构成长度为1的LIS
int maxLen = 1;
for (int i = 1; i < n; i++) {
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;
}
/**
* O(n log n) 优化解法：patience sorting + 二分查找
*/
public static int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// tails[k] 表示长度为 k+1 的上升子序列的最小末尾元素
int[] tails = new int[n];
int size = 0;
for (int num : nums) {
// 二分查找：找到第一个 >= num 的位置
int left = 0, right = size;
while (left < right) {
int mid = (left + right) >>> 1;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
if (left == size) size++;
}
return size;
}
/**
* O(n log n) 解法并重构具体的LIS序列
*/
public static List<Integer> getLIS(int[] nums) {
int n = nums.length;
if (n == 0) return new ArrayList<>();
int[] tails = new int[n]; // tails数组的值
int[] tailIndices = new int[n]; // tails中每个位置对应原数组的索引
int[] prev = new int[n]; // 记录前驱节点，用于重构路径
Arrays.fill(prev, -1);
int size = 0;
for (int i = 0; i < n; i++) {
int left = 0, right = size;
while (left < right) {
int mid = (left + right) >>> 1;
if (tails[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = nums[i];
tailIndices[left] = i;
if (left > 0) {
prev[i] = tailIndices[left - 1];
}
if (left == size) size++;
}
// 从最后一个元素回溯重构LIS
List<Integer> lis = new ArrayList<>();
int idx = tailIndices[size - 1];
while (idx != -1) {
lis.add(nums[idx]);
idx = prev[idx];
}
Collections.reverse(lis);
return lis;
}
/**
* 最长非降子序列（允许相等）
*/
public static int lengthOfLNDS(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] tails = new int[n];
int size = 0;
for (int num : nums) {
// 注意：非降序要求找到第一个 > num 的位置（upper_bound）
int left = 0, right = size;
while (left < right) {
int mid = (left + right) >>> 1;
if (tails[mid] <= num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
if (left == size) size++;
}
return size;
}
/**
* 最长下降子序列（反向做LIS即可）
*/
public static int lengthOfLDS(int[] nums) {
int[] reversed = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
reversed[i] = -nums[i]; // 取反后求LIS
}
return lengthOfLIS(reversed);
}
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("数组: " + Arrays.toString(nums));
System.out.println("LIS长度 (O(n^2)): " + lengthOfLIS_DP(nums));
System.out.println("LIS长度 (O(n log n)): " + lengthOfLIS(nums));
System.out.println("具体LIS序列: " + getLIS(nums));
System.out.println("最长非降子序列长度: " + lengthOfLNDS(nums));
System.out.println("最长下降子序列长度: " + lengthOfLDS(nums));
// 测试重复元素
int[] nums2 = {1, 1, 1, 1, 1};
System.out.println("\\n数组: " + Arrays.toString(nums2));
System.out.println("LIS长度 (严格递增): " + lengthOfLIS(nums2));
System.out.println("LNDS长度 (非降): " + lengthOfLNDS(nums2));
}
}
复杂度分析
- O(n²) DP：时间 O(n²)，空间 O(n)。适合小规模数据或需要统计方案数的场景。
- O(n log n) 优化：时间 O(n log n)，空间 O(n)。通过维护
tails数组和二分查找，是工程实践中的标准做法。 - 重构路径：额外使用 O(n) 空间记录前驱索引。
应用场景
LIS 及其扩展问题广泛应用于多个领域：在卡牌游戏中分析最优出牌序列；在生物信息学中比较基因序列的相似性；在机器学习中分析时间序列的单调趋势；在数据库查询优化中确定索引的最优组合顺序。掌握 LIS 的 O(n log n) 优化技巧，也是理解 patience sorting、 Dilworth 定理和在线二分图匹配等高级算法的起点。
