将 1~N 的排列依次分配到两个变量上，最大化"当前值小于新值"的计数。核心结论：前缀最大值必贡献，剩余元素的最大贡献数为其 LIS 长度，答案 = 前缀最大值个数 + LIS(剩余序列)，时间复杂度 O(N log N)。

LIS 最长上升子序列的线性 DP 学习笔记，涵盖 O(n²) 朴素动态规划推导、最优子结构与无后效性分析、NOIP 2004 合唱队形例题，以及 O(n log n) 的 Patience Sorting（二分贪心）优化与常见误区。

1. 题目数据 (Problem Metadata) 题目类型：传统题 题目链接：Problem - 670C - Codeforces 时间限制：2 秒 内存限制：256 MB 2. 题意简述 (Problem Summary) 给定 $n...

1. 题目数据 题目类型：传统题 题目链接：4002. 统计有效序列数目 - 力扣（LeetCode） 2. 题意简述 给定正整数 $n$ 与 $k$，求长度为 $k$ 的正整数序列 $(a_1, a_2, \dots, a_k)$ 的个数，...

LeetCode 3501「操作后最大活跃区段数 II」题解，基于 I 版结论将交易转化为相邻 0 块合并，用 Sparse Table 预处理相邻 0 块长度和的区间最大值，支持 O(log n) 单次查询。

1. 题目数据 (Problem Metadata) 题目类型：传统题 题目链接：P14361 [CSP-S 2025] 社团招新 - 洛谷 时间限制：1.00s 内存限制：512.00MB 2. 题意简述 (Problem Summary)...

1. 题目数据 (Problem Metadata) 题目类型：传统题 题目链接：3499. 操作后最大活跃区段数 I - 力扣（LeetCode） 2. 题意简述 (Problem Summary) 给定长度为 $n$（$1 \le n \...

1. 题目数据 (Problem Metadata) 题目类型：传统题 题目链接：Problem - 26B - Codeforces 时间限制：5 秒 内存限制：256 MB 2. 题意简述 (Problem Summary) 给定长度为 ...

经典「最大化最小值」二分答案 + 贪心判定问题，NOIP 2015 提高组，通过二段性将枚举转化为判定，时间复杂度 O(N log L)。