【动态规划5】最长上升子序列

解题思路

本题要求在一个整数序列中找到一个最长的上升子序列，并输出其长度。一个子序列是由原序列中若干个元素（可以不连续）组成的，而上升子序列则要求每一个元素都大于它前面的元素。我们可以使用动态规划的方法高效解决这个问题。通过逐步分析，建立状态转移方程，最终找到最长上升子序列的长度。

Step1: 讨论 $n=3$ 的情况

题目描述：

给定一个整数序列，求该序列的最长上升子序列的长度。一个子序列是由原序列中若干个元素（可以不连续）组成的，而上升子序列则要求每一个元素都大于它前面的元素。

输入描述：

• 第一行包含一个整数 $n$，表示序列的长度 $(1 \leq n \leq 1000)$。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的元素 $(1 \leq a_i \leq 10^9)$。

输出描述：

输出一个整数，表示序列的最长上升子序列的长度。

样例输入：

6
10 9 2 5 3 7

样例输出：

3

提示：

在样例中，最长上升子序列为 [2, 5, 7]，其长度为 3。