LIS（Longest Increasing Subsequence）是线性DP的经典题型。给定一个序列，找出其中严格递增的最长子序列长度。注意：子序列不要求连续，但要保持相对顺序。
核心思路：dp[i] = 以第 i 个元素结尾的最长上升子序列长度。转移方程：
dp[i] = max(dp[j] + 1)，其中 0 ≤ j < i 且 a[j] < a[i]。即在 i 之前找所有比 a[i] 小的元素，取它们 dp 值的最大值加 1。dp[i] = 1。
时间复杂度 O(n²)，n ≤ 1000 时可直接用。更优的 O(n log n) 解法可用二分+贪心优化。
// 和 LIS 完全对称，只是判断条件反过来
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
int a[1010], dp[1010];
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) dp[i] = 1; // 初始化
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (a[j] > a[i]) // 关键：严格递减
dp[i] = max(dp[i], dp[j] + 1);
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, dp[i]);
cout << ans << endl;
// 输入：6 5 3 4 2 1 6
// 输出：4 （拦截序列 5 3 2 1）
}
a[j] < a[i] 改成 a[j] > a[i]。> 改成 >=。a[j] < a[i]，如果允许相等就用 a[j] <= a[i]，审题要仔细！max(dp[0..n-1])。