原始题目
int n = a.size();
vector<int> inc(n, 1), dec(n, 1);
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
if (a[j] < a[i]) inc[i] = max(inc[i], inc[j] + 1);
for (int i = n-1; i >= 0; i--)
for (int j = n-1; j > i; j--)
if (a[j] < a[i]) dec[i] = max(dec[i], dec[j] + 1);
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, inc[i] + dec[i] - 1);
问：这段代码求的是什么？
答案
求数组 a 的 最长比特尼克子序列（Longest Bitonic Subsequence, LBS）的长度。
比特尼克序列 = 先严格递增、再严格递减的子序列；ans 即其最大长度。
解析
| 数组 | 含义 | 计算方向 |
|---|---|---|
inc[i] |
以 i 结尾的最长上升子序列（LIS）长度 |
从左往右扫 |
dec[i] |
以 i 开头（向右）的最长下降子序列（LDS）长度 |
从右往左扫 |
inc[i]+dec[i]-1 |
以 i 为峰值的比特尼克子序列长度 |
峰值在两段各算一次，需 -1 去重 |
最后 ans = max(...) 取所有峰值中的最大值。
走一遍示例
a = [1, 11, 2, 10, 4, 5, 2, 1]
- 第一轮（左→右）得到
inc = [1,2,2,3,3,4,2,1] - 第二轮（右→左）得到
dec = [1,5,3,4,3,3,2,1] - 峰值合并：
inc+dec-1 = [1,6,4,6,5,6,3,1] ans = 6，对应比特尼克序列1, 2, 10, 5, 2, 1。
易错点总结
- 比特尼克是“子序列”不是“子数组”：不要求元素连续。若要连续的，是另一道题（最长峰形子数组）。
-1不能省：峰值i在inc和dec里都被算了一次，合并时要减 1。dec的方向：它是“以i开头的下降子序列”，所以要从右往左扫，判断条件是a[j] < a[i]（j 在 i 右侧）。- 复杂度：
O(n²)，可优化到O(n log n)，但竞赛初赛题里O(n²)写法最常见。
思考题
如果把第二个循环里的 a[j] < a[i] 改成 a[j] <= a[i]，结果会变吗？为什么？
