子序列问题

📝 1. 最长上升子序列

给出一个由 $ n(n\le 5000) $ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的 最长上升子序列 的长度。

💡 解题思路

• 状态设计：$f_i$ 代表以 $i$ 结尾的最长上升子序列的长度。
• 转移：

\[ f_i = \max(f_i, f_j + 1),\ j<i\ \text{且}\ a_j< a_i \]

• 初始化：$f_i = 1$。
• 答案：$\max_{i=1}^n f_i$

🔢 复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

✅ 代码实现

for (int i = 1; i <= n; i++) 
{
    f[i] = 1;
    for (int j = 1; j < i; j++) 
    {
        if (a[i] > a[j]) 
        {
            f[i] = max(f[i], f[j] + 1);
        }
    }
    ans = max(ans, f[i]);
}

---

📝 2. 最长不下降子序列

给出一个由 $ n(n\le 5000) $ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的 最长不下降子序列 的长度。

• 不下降指的是相邻元素可以相等。

💡 解题思路

• 状态设计：$f_i$ 代表以 $i$ 结尾的最长不下降子序列的长度。
• 转移：

\[ f_i = \max(f_i, f_j + 1),\ j<i\ \text{且}\ a_j\leq a_i \]

• 初始化：$f_i = 1$。
• 答案：$\max_{i=1}^n f_i$

🔢 复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

✅ 代码实现

for (int i = 1; i <= n; i++) 
{
    f[i] = 1;
    for (int j = 1; j < i; j++) 
    {
        if (a[i] >= a[j]) 
        {
            f[i] = max(f[i], f[j] + 1);
        }
    }
    ans = max(ans, f[i]);
}

---

📝 3. 最长下降子序列

给出一个由 $ n(n\le 5000) $ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的 最长下降子序列 的长度。

💡 解题思路

• 状态设计：$f_i$ 代表以 $i$ 结尾的最长下降子序列的长度。
• 转移：

\[ f_i = \max(f_i, f_j + 1),\ j<i\ \text{且}\ a_j> a_i \]

• 初始化：$f_i = 1$。
• 答案：$\max_{i=1}^n f_i$

🔢 复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

✅ 代码实现

for (int i = 1; i <= n; i++) 
{
    f[i] = 1;
    for (int j = 1; j < i; j++) 
    {
        if (a[i] < a[j]) 
        {
            f[i] = max(f[i], f[j] + 1);
        }
    }
    ans = max(ans, f[i]);
}

---

📝 4. 最长不上升子序列

给出一个由 $ n(n\le 5000) $ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的 最长不上升子序列 的长度。

💡 解题思路

• 状态设计：$f_i$ 代表以 $i$ 结尾的最长不上升子序列的长度。

• 转移：

\[ f_i = \max(f_i, f_j + 1),\ j<i\ \text{且}\ a_j\geq a_i \]

• 初始化：$f_i = 1$。
• 答案：$\max_{i=1}^n f_i$

🔢 复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

✅ 代码实现

for (int i = 1; i <= n; i++) 
{
    f[i] = 1;
    for (int j = 1; j < i; j++) 
    {
        if (a[i] <= a[j]) 
        {
            f[i] = max(f[i], f[j] + 1);
        }
    }
    ans = max(ans, f[i]);
}

---