问题描述

给定一个无序的整数序列a[0…n-1]，求其中最长递增子序列的长度。

例如，a[]={2，1，5，3，6，4，8，9，7}，n=9，其最长递增子序列为{1，3，4，8，9}，结果为5。

问题求解

设计动态规划数组为一维数组dp，dp[i]表示a[0…i]中以a[i]结尾的最长递增子序列的长度。对应的状态转移方程如下：

求出dp后，其中最大元素即为所求。

代码

int a[] = {2,1,5,3,6,4,8,9,7 };int n = sizeof(a) / sizeof(a[0]);int ans = 0;int dp[MAXN];void solve(int a[], int n){int i, j;for (i = 0; i < n; i++){dp[i] = 1;for (j = 0; j < i; j++){if (a[i] > a[j])dp[i] = max(dp[i], dp[j] + 1);}}ans = dp[0];for (i = 1; i < n; i++)ans = max(ans, dp[i]);}

算法分析

solve()算法中含两重循环，时间复杂度为O(n2)。