最长递增子序列（Longest Increasing Subsequence）是动态规划的经典问题，从 O(n²) DP 到 O(n log n) 贪心+二分，体现了算法优化的完整思路。
一、问题定义
Mermaid · 渲染中（下方为源码）
graph LR A[LIS] --> B[O(n²) DP] A --> C[O(n log n) 贪心+二分]
给定数组 nums，找出最长的严格递增子序列的长度（子序列不要求连续）。
输入: [10, 9, 2, 5, 3, 7, 101, 18]
输出: 4 （[2, 3, 7, 101]）
二、O(n²) 动态规划
状态定义
dp[i] = 以 nums[i] 结尾的 LIS 长度
转移方程
dp[i] = max(dp[j] + 1)，对所有 j < i 且 nums[j] < nums[i]
实现
int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
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;
}