【题目来源】
AcWing：896. 最长上升子序列 II - AcWing题库
【题目描述】
给定一个长度为 \(N\) 的数列，求数值严格单调递增的子序列的长度最长是多少。
【输入】
第一行包含整数 \(N\)。
第二行包含 \(N\) 个整数，表示完整序列。
【输出】
输出一个整数，表示最大长度。
【输入样例】
7
3 1 2 1 8 5 6
【输出样例】
4
【解题思路】
【算法标签】
《AcWing 896 最长上升子序列II》 #贪心#
【代码详解】
// 引入所有标准库头文件，方便使用各种标准库功能
#include <bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀
using namespace std;// 定义常量
const int N = 100010; // 数组最大长度为100010// 定义全局变量
int n; // n: 输入序列的长度
int a[N]; // a[N]: 存储输入的整数序列
int q[N]; // q[i]: 表示上升子序列长度为 i 时，序列末端的最小值// 主函数，程序的入口点
int main()
{// 读取序列的长度 ncin >> n;// 循环读取序列中的每个元素，并存储到数组 a[i] 中for (int i = 0; i < n; i++)cin >> a[i]; // 读入序列// 初始化已经求出的最大上升子序列长度为 0int len = 0; // 已经求出的最大上升子序列长度// 动态规划结合二分查找，计算最长上升子序列的长度for (int i = 0; i < n; i++) {// 初始化二分查找的左右边界int l = 0, r = len;// 使用二分查找确定当前元素 a[i] 可以放置的上升子序列位置while (l < r) {// 计算中间位置，防止漏掉 mid，需要 +1int mid = (l + r + 1) / 2;// 如果 q[mid] 小于 a[i]，说明 a[i] 可以接在长度为 mid 的子序列后面if (q[mid] < a[i])l = mid; // 更新左边界为 midelser = mid - 1; // 否则，更新右边界为 mid - 1}// 将当前元素 a[i] 放置在上升子序列长度为 r + 1 的位置，更新 q[r + 1]q[r + 1] = a[i];// 更新已经求出的最大上升子序列长度len = max(len, r + 1);}// 输出最长上升子序列的长度cout << len << endl;// 程序正常结束，返回 0return 0;
}
【运行结果】
7
3 1 2 1 8 5 6
4