📌 二分优化 LIS

---

🧠 核心思想

特点：对于一个固定的长度来说，此时结尾的数字越小越好，越小的数字对于后续的数字才有更多的可能性。

使用一个辅助数组 d[] 优化 LIS 的求解，使时间复杂度从 $O(n^2)$ 降低到 $O(n\log n)$。

---

📘 关键概念与定义

🔹 辅助数组 d[]

• d[i] 表示 长度为 $i$ 的上升子序列 中，结尾元素的最小值。
• 保持 d[] 单调递增：$d[1] < d[2] < d[3] < \cdots$。

例：对于 $a = [3, 1, 2, 4]$，最终可得：

• $d_1 = 1$
• $d_2 = 2$
• $d_3 = 4$

$d_i$ 的含义是长度为 $i$ 的上升子序列结尾的最小数值。其值必然大于 $d_{i-1}$。否则就有明显矛盾，没法满足上升关系。

---

⚙️ 实现逻辑

🔍 更新规则

1. 初始化：len = 0（当前 LIS 长度）
2. 遍历每个元素 a[i]：
   • 若 a[i] > d[len]：直接扩展序列，d[++len] = a[i]
   • 否则：使用 lower_bound 在 d[1...len] 中找到第一个 ≥ a[i] 的位置 pos，更新 d[pos] = a[i]

现在求解以 $a[i]$ 结尾的最长上升子序列。因此 $a[i]$ 拼接到最后一个小于a[i] 的后面。 那么应该在 $d$ 数组中找到刚好大于等与 a[i] 的位置记作 pos，然后更新 d[pos] = a[i]。 在往后的位置没法更新为 a[i]，因为更新了就不满足上升的关系。 往前的更小的位置被更新了，以 $i$ 结尾的 LIS 长度就会缩短。

✅ C++ 示例代码

for (int i = 1; i <= n; i++) 
{
    if (a[i] > d[len]) 
    {
        d[++len] = a[i];
        f[i] = len;
    } 
    else 
    {
        int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
        d[pos] = a[i];
        f[i] = pos;
    }
}

---

📈 拓展变形问题

---

1️⃣ 最长不下降子序列（Non-Decreasing Subsequence）

• 若 a[i] >= d[len]：放到 d[++len]
• 否则：使用 upper_bound 找第一个大于 a[i] 的位置 pos，更新 d[pos] = a[i]

for (int i = 1; i <= n; i++) {
    if (a[i] >= d[len]) 
    {
        d[++len] = a[i];
        f[i] = len;
    } 
    else 
    {
        int pos = upper_bound(d + 1, d + len + 1, a[i]) - d;
        d[pos] = a[i];
        f[i] = pos;
    }
}

---

2️⃣ 最长下降子序列（Strictly Decreasing Subsequence）

• 若 a[i] < d[len]：放到 d[++len]
• 否则：用自定义二分查找 <= a[i] 的位置 pos，更新 d[pos] = a[i]

for (int i = 1; i <= n; i++) {
    if (a[i] < d[len]) 
    {
        d[++len] = a[i];
        f[i] = len;
    } 
    else 
    {
        int l = 1, r = len, pos = 0;
        while (l <= r) 
        {
            int mid = (l + r) >> 1;
            if (d[mid] <= a[i]) pos = mid, r = mid - 1;
            else l = mid + 1;
        }
        d[pos] = a[i];
        f[i] = pos;
    }
}

---

3️⃣ 最长不上升子序列（Non-Increasing Subsequence）

• 若 a[i] <= d[len]：放到 d[++len]
• 否则：使用自定义二分查找 < a[i] 的位置 pos，更新 d[pos] = a[i]

for (int i = 1; i <= n; i++) 
{
    if (a[i] <= d[len]) 
    {
        d[++len] = a[i];
        f[i] = len;
    } 
    else 
    {
        int l = 1, r = len, pos = 0;
        while (l <= r) 
        {
            int mid = (l + r) >> 1;
            if (d[mid] < a[i]) pos = mid, r = mid - 1;
            else l = mid + 1;
        }
        d[pos] = a[i];
        f[i] = pos;
    }
}

---

📝 小结对比

序列类型	放置条件	查找方式
严格上升 LIS	a[i] > d[len]	lower_bound
不下降序列	a[i] >= d[len]	upper_bound
严格下降序列	a[i] < d[len]	手写 <= 二分
不上升序列	a[i] <= d[len]	手写 < 二分

---

点我下载课件