🏔️ 最长山形子序列（Longest Bitonic Subsequence, LBS）

📘 题目描述

给定一个长度为 n 的整数数组 a[1..n]，请你找出一个最长的山形子序列的长度。

所谓山形子序列，要求是一个先严格递增，后严格递减的子序列。例如：

• [1, 3, 5, 4, 2] 是一个山形序列。
• [1, 2, 3] 不是山形序列（没有下降）。
• [3, 2, 1] 不是山形序列（没有上升）。

📥 输入格式

• 第一行一个整数 n（1 ≤ n ≤ 1000）
• 第二行 n 个整数 a[1] ~ a[n]

📤 输出格式

• 输出一个整数，表示最长山形子序列的长度。

💡 输入输出样例

输入样例 #1

7
1 5 3 4 8 6 7

输出样例 #1

5

解释：最长山形子序列为 [1, 3, 4, 8, 7]。

输入样例 #2

8
10 20 30 40 50 40 30 20

输出样例 #2

8

🧠 解题思路

我们用动态规划的方法：

1. 定义两个数组：
   • inc[i]：表示以 a[i] 结尾的最长递增子序列长度。
   • dec[i]：表示以 a[i] 开始的最长递减子序列长度。
2. 计算递增子序列 inc[i]：

   for (int i = 1; i <= n; ++i)
       for (int j = 1; j < i; ++j)
           if (a[j] < a[i])
               inc[i] = max(inc[i], inc[j] + 1);
   

3. 计算递减子序列 dec[i]（反向处理）：

   for (int i = n; i >= 1; --i)
       for (int j = n; j > i; --j)
           if (a[j] < a[i])
               dec[i] = max(dec[i], dec[j] + 1);
   

4. 最终结果：

   max(inc[i] + dec[i] - 1)
   

🔍 边界测试建议