原题链接：
这是一道动态规划问题 ，首先我们建立一个dp数组，来记录上升序列的长度。
dp[ i ]表示以第 i 个数结尾的上升序列序列长度，最后dp数组中的最大值就是最长上升序列的长度，状态转移方程如下：
dp[ i ] = max( dp[ j ] ) + 1,其中0 ≤ j < i且num[ j ] < num[ i ]
因为最短的序列长度都是1，所以我们可以将dp数组全部初始化为1 。
完整代码如下：
#include<stdio.h> int main() { int n; scanf("%d",&n); int arr[n]; int dp[n]; for(int i = 0 ; i < n ; i++){ scanf("%d",&arr[i]); dp[i] = 1; } int max = 0; for(int i = 1 ; i < n ; i++){ for(int j = 0 ; j < i ; j++){ if(arr[i] > arr[j]){ if(dp[j] > max){ max = dp[j]; } } } dp[i] += max; max = 0; } max = 0; for(int i = 0 ; i < n ; i++){ if(max < dp[i]) max = dp[i]; } printf("%d" , max ); }
