动态规划之线性dp之最长上升子序列

问题

这是经典的 LIS 问题

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

分析

那么考虑动态规划，我们设计一个 dp[i] 数组，表示以数组第i个元素（a[i]）为结尾的最长上升子序列的长度。

为什么要 “以a[i]结尾”？因为 LIS 是严格递增的，后续元素要接在a[i]后面，必须满足比a[i]大，这样才能通过dp[i]推导后续状态。

从第一个数字开始推，所以说，dp[i] = 1 是关键初始化，因为每个元素本身可以单独构成一个长度为 1 的上升子序列，所以所有dp[i]的初始值都是 1。

那么我们需要遍历 i 之前的所有元素 j (从 0 到 i-1)，对于每个i，遍历它前面所有的元素j：

如果a[i] > a[j]（满足 “上升” 条件），说明a[i]可以接在以a[j]结尾的 LIS 后面，此时dp[i]可以更新为dp[j] + 1。
取所有满足条件的dp[j] + 1的最大值，就是dp[i]的最终值（即dp[i] = Math.max(dp[i], dp[j] + 1)）。

这就得到了状态转移方程，还是比较好理解的

模板代码

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = scanner.nextInt();

        for(int i = 1; i <= n; i++) dp[i] = 1;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                // 在i的前面找到小于a[i]的数字a[j]
                // 用对于的dp值更新dp[i]
                if(a[i] > a[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        for(int i = 1; i <= n; i++){
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);

        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);  // 存储序列元素（1-based索引）
    vector<int> dp(n + 1, 1);  // dp[i]表示以a[i]结尾的最长递增子序列长度，初始化为1

    // 读取输入序列
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // 计算最长递增子序列
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            // 若前面的元素a[j]小于当前元素a[i]，则可以构成更长的子序列
            if (a[i] > a[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // 查找最大的dp值，即最长递增子序列的长度
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res = max(res, dp[i]);
    }

    cout << res << endl;

    return 0;
}

二分+贪心优化

优化思路

情况不太情况，我们的上面的基于线性DP的代码时间复杂度是 O (n²)，适合n <= 1000的场景。如果n达到1e5，就会超时，此时需要用贪心 + 二分查找优化到 O (n log n)

怎么优化？

你问住我了

维护一个辅助数组tails，tails[k]表示，所有长度为k+1的上升子序列中，结尾元素最小的值

这个有什么用呢？这就是贪心的利用。用 “贪心思想” 维护辅助数组

因为用 “最小可能结尾元素” 可以保留更多后续拓展空间，比如长度为 3 的 LIS，结尾是 2 比结尾是 5 更好，后续更容易接更大的元素

也还需要维护一个变量，len，len表示当前找到的 LIS 的最大长度。

初始时len=0（没有有效元素），b[0]设为极小值（哨兵）。
当新元素a[i]大于b[len]时，说明能形成更长的 LIS，len会 + 1（比如b[len]是长度len的结尾，a[i]接在后面，长度变成len+1）。

那么二分查找的优化又是怎么个事？

在 tails数组的有效区间[0, len]内，找到第一个大于等于x（即a[i]）的元素的索引r。

我的二分写法是 “左闭右开” 的变种（l=-1, r=len，循环条件l+1 < r）：

初始l=-1（左边界外），r=len（右边界，b[r]未使用）。
每次计算mid = l + r >> 1（等价于(l+r)/2，位运算更快）。
如果b[mid] >= x：目标在左半区，r=mid（收缩右边界）。
如果b[mid] < x：目标在右半区，l=mid（收缩左边界）。
循环结束时，r就是第一个大于等于x的索引（比如b=[-inf,1,3,5]，x=4，会找到r=2，对应b[2]=3？不，b[2]=3 <4，b[3]=5 >=4，所以r=3）。

模板代码

Java

import java.util.Scanner;

public class Main {
    private static final int N = 100010;
    private static int n, len;
    private static int[] a = new int[N], b = new int[N];

    private static int find(int x) {
        int l = -1, r = len;
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (b[mid] >= x) r = mid;
            else l = mid;
        }
        return r;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i = 0; i < n; i++) a[i] = sc.nextInt();

        b[0] = -999999998;     //哨兵
        for (int i = 0; i < n; i++) {
            if (b[len] < a[i]) b[++len] = a[i];    // 新数大于队尾数，则插入队尾
            else b[find(a[i])] = a[i];    // 替换第一个大于等于a[i]的数(贪心)
        }

        System.out.println(len);
        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

const int N = 100010;
int n, len;
int a[N];
int b[N];  // 存储最长上升子序列的优化数组

// 二分查找：找到第一个大于等于x的位置
int find(int x) {
    int l = -1, r = len;
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;  // 等价于 l + r >> 1，避免溢出
        if (b[mid] >= x) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    b[0] = -999999998;  // 哨兵，确保第一个元素能正常插入
    len = 0;  // 初始长度为0
    
    for (int i = 0; i < n; ++i) {
        if (b[len] < a[i]) {
            // 新元素大于当前最长序列的末尾，直接扩展
            b[++len] = a[i];
        } else {
            // 替换第一个大于等于当前元素的位置，维持序列单调性
            int pos = find(a[i]);
            b[pos] = a[i];
        }
    }
    
    cout << len << endl;
    return 0;
}

python

import bisect

n = int(input())
a = list(map(int, input().split()))

# b存储最长上升子序列的优化数组，初始加入哨兵
b = [-999999998]
len_b = 0  # 记录有效长度（不含哨兵）

for num in a:
    if num > b[-1]:
        # 新元素大于当前末尾，扩展序列
        b.append(num)
        len_b += 1
    else:
        # 二分查找第一个大于等于num的位置并替换
        # bisect_left返回第一个>=num的索引（与原find函数逻辑一致）
        pos = bisect.bisect_left(b, num)
        b[pos] = num

print(len_b)

如果要改成 “最长非递减子序列”，只需把find函数中的b[mid] >=x改成b[mid] >x，同时把b[len] <a[i]改成b[len] <=a[i]。

举例分析流程

用样例a = [3,1,2,4,5]（LIS 长度 4），模拟代码执行过程：

初始化：b[0] = -inf，len=0，a = [3,1,2,4,5]。
处理a[0]=3
- b[len] = b[0] = -inf < 3，执行b[++len] = 3 → len=1，b=[-inf,3]。
处理a[1]=1
- b[len] = 3 >=1，调用find(1)：找b[0..1]中第一个≥1 的索引。
  - l=-1, r=1 → mid=0，b[0]=-inf <1 → l=0。
  - 循环结束，r=1 → 替换b[1] =1 → b=[-inf,1]，len仍为 1。
处理a[2]=2
- b[len] =1 <2，执行b[++len] =2 → len=2，b=[-inf,1,2]。
处理a[3]=4
- b[len] =2 <4，执行b[++len] =4 → len=3，b=[-inf,1,2,4]。
处理a[4]=5
- b[len] =4 <5，执行b[++len] =5 → len=4，b=[-inf,1,2,4,5]。
最终输出len=4，与 LIS 长度一致。

例题

题目

[P1091 [NOIP 2004 提高组] 合唱队形][https://www.luogu.com.cn/problem/P1091]

P1091 [NOIP 2004 提高组] 合唱队形

题目描述

n 位同学站成一排，音乐老师要请其中的 n − k 位同学出列，使得剩下的 k 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 k 位同学从左到右依次编号为 1, 2, … , k，他们的身高分别为 t₁, t₂, … , t_k，则他们的身高满足 t₁ < ⋯ < t_i > t_i + 1> … > t_k(1 ≤ i ≤ k)。

你的任务是，已知所有 n 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式

共二行。

第一行是一个整数 n（2 ≤ n ≤ 100），表示同学的总数。

第二行有 n 个整数，用空格分隔，第 i 个整数 t_i（130 ≤ t_i ≤ 230）是第 i 位同学的身高（厘米）。

输出格式

一个整数，最少需要几位同学出列。

输入输出样例 #1

输入 #1
1
2
8
186 186 150 200 160 130 197 220
输出 #1
1
4
说明/提示

对于 50% 的数据，保证有 n ≤ 20。

对于全部的数据，保证有 n ≤ 100。

题目分析

可以发现，这道题目不是严格意义上的 LIS，是找到 “先上升后下降” 的最长合唱队形

用最少出列人数 = 总人数 - 最长合唱队形长度。采用二分贪心的 O (n log n) 解法，分别计算每个位置的 “左侧最长上升子序列（LIS）长度” 和 “右侧最长下降子序列（LDS）长度”，再通过两者求和找最大值。

整理一下核心思路

合唱队形的本质是：存在一个 “峰值” 位置i，使得：

从左到i是严格上升的（LIS）；
从i到右是严格下降的（LDS）；
最长合唱队形长度 = LIS [i] + LDS [i] - 1（峰值i被重复计算，需减 1）。

最少出列人数 = n - 最长合唱队形长度。

首先，定义 left[i]，以第i个元素为峰值，左侧（从 0 到 i）的最长严格上升子序列长度。

然后，定义right[i]，以第i个元素为峰值，右侧（从 i 到 n-1）的最长严格下降子序列长度。

严格下降等价于 “反转后严格上升”，所以可以：
1. 把数组从右到左遍历（或反转数组）；
2. 计算 “最长严格上升子序列”，结果就是原数组的 “最长严格下降子序列”。

遍历每个位置i，计算left[i] + right[i] - 1，取最大值即为最长合唱队形长度。

最少出列人数 = n - 最长合唱队形长度。

题解代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
        }

        // 步骤1：计算left数组（每个位置的左侧最长严格上升子序列长度）
        int[] left = getLIS(t);

        // 步骤2：计算right数组（每个位置的右侧最长严格下降子序列长度）
        int[] reversedT = reverseArray(t); // 反转数组
        int[] reversedRight = getLIS(reversedT); // 反转数组的LIS = 原数组的LDS
        int[] right = reverseArray(reversedRight); // 再反转回来，得到right数组

        // 步骤3：找最长合唱队形长度
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            int current = left[i] + right[i] - 1;  // 峰值重复计算，减1
            if (current > maxLen) maxLen = current;
        }

        // 步骤4：最少出列人数 = 总人数 - 最长合唱队形长度
        System.out.println(n - maxLen);
        sc.close();
    }

    // 二分贪心计算最长严格上升子序列（LIS）的长度数组
    private static int[] getLIS(int[] t) {
        int n = t.length;
        // 存储每个位置的LIS长度
        int[] lenArr = new int[n];
        // 辅助数组：tails[k]是长度为k+1的LIS的最小结尾
        int[] tails = new int[n];
        // 指针，当前tails的有效长度
        int len = 0;

        for(int i = 0; i < n; i++) {
            int x = t[i];
            // 二分查找tails中第一个 >= x的位置（严格上升，所以找>=）
            int l = -1, r = len;

            while (l + 1 < r) {
                int mid = l + r >> 1;
                if(tails[mid] >= x) {
                    r = mid;
                }else{
                    l = mid;
                }
            }

            tails[r] = x;
            // 更新当前位置的LIS长度（r+1，因为tails[0]对应长度1）
            lenArr[i] = r + 1;
            // 记得更新浮标
            if (r == len) {
                len++;
            }
        }

        return lenArr;
    }


    // 反转数组（用于计算LDS）
    private static int[] reverseArray(int[] arr) {
        int n = arr.length;
        int[] reversed = new int[n];
        for (int i = 0; i < n; i++) {
            reversed[i] = arr[n - 1 - i];
        }
        return reversed;
    }
}