📘 最长不下降子序列（LNDS）

📝 题目描述

给定一个长度为 n 的整数序列 a[1..n]，如果存在一组下标满足：

1 ≤ i₁ < i₂ < ... < iₖ ≤ n 且 a[i₁] ≤ a[i₂] ≤ ... ≤ a[iₖ]

那么该子序列称为一个 ​不下降子序列​。请你编写程序，求出其中最长不下降子序列的长度（LNDS）。

📥 输入格式

第一行一个整数 n，表示数组长度（1 ≤ n ≤ 1000）

第二行 n 个用空格分隔的整数，表示数组元素。

📤 输出格式

一个整数，表示最长不下降子序列的长度。

💡 输入输出样例

【输入样例】

4
1 3 1 2

【输出样例】

3

解释：最长不下降子序列是 [1, 1, 2] ，长度为 3。

🧠 解题思路（动态规划）

• 定义 dp[i] 表示以第 i 个元素结尾的最长不下降子序列的长度；
• 初始化：dp[i] = 1，每个元素都可单独成序列；
• 状态转移：

  if (a[j] <= a[i]) {
      dp[i] = max(dp[i], dp[j] + 1);
  }
  

• 最终答案是 max(dp[1..n])。

✅ 时间与空间复杂度

• 时间复杂度：O(n²)
• 空间复杂度：O(n)