问题描述
给定一个无序的整数序列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)。