题目描述
求N个数的最长上升子序列。
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
动态规划
动态规划分析
- 状态定义
集合 dp[i] 以数字a[i]为结尾的所有上升子序列
集合属性 Max - 状态划分/计算
对于以a[i]为结尾的最长上升子序列,其前一个数可以取a[1] ~ a[i] a[i]表示上升子序列为1
有些集合划分的思考个人感觉类似bfs的想法,即考虑哪些状态走一步到达当前状态。对于以a[i]结尾
的上升子序列,其最近的一步就是以a[k]为a[i]的前一个的上升子序列。
3.具体实现
对于i,求Max(dp[j]+1) 也就是以a[j]作为a[i]的前一个数的上升子序列
注意有些j可能不合法(不符合我们对集合的定义 即aj>=ai)
时间复杂度
状态数 N
状态转移数 N
时间复杂度O(N^2) 1e10 超时
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int Max_N = 1e5+10;
int n;
int a[Max_N];
int dp[Max_N];
int main()
{
cin >> n;
for(int i=0; i<n; i++ ) cin >> a[i];
for( int i=0; i<n; i++ )
{
dp[i] = 1; //最小为1
for( int j=0; j<i; j++ )
{
if( a[j]<a[i] ) dp[i] = max( dp[i], dp[j]+1 );
}
}
int res = 0;
for( int i=0; i<n; i++ ) res = max( res, dp[i] );
cout << res << endl;
return 0;
}
优化版 贪心
分析动态规划求解中的冗余计算
对于样例
7
3 1 2 1 8 5 6 a数组
1 2 3 4 5 6 7 i //下标
dp[1] = dp[2] = 1
当求dp[5]也就是8的最长上升子序列时,我们重复计算了长度为1的dp[1]和dp[2]
而对于长度为1的上升子序列 1 和 3 ,如果ai可以接在3后面那么也一定能接在1后面,
所以我们可以只保存1,也就是对于相同长度的最长上升子序列,我们只保存末尾值最小的。
实现
维护一个符合上述贪心思想的最长上升子序列,因为序列中每个元素都是递增的(最长上升子序列定义),所以
对于ai我们可以找到最后一个小于ai的aj,将aj+1更新为ai。(因为长度相同,且ai<=aj+1)
时间复杂度
遍历数组 N
二分 logN 更新O(1)
时间复杂度O(N*logN)
C++代码 1
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 2e9;
const int Max_N = 1e5+10;
int n;
int a[Max_N];
int dp[Max_N]; //dp[i] 长度为i符合贪心思想的上升子序列(末尾值最小)
int main()
{
cin >> n;
for( int i=0; i<n; i++ ) cin >> a[i];
int len = 0; //最长上升子序列长度(dp中元素个数)
dp[0] = -INF; //作为左端点 任何值都>-INF
for( int i=0; i<n; i++ )
{
int l = 0, r = len; //二分模板2 找<a[i]的最大 即最右端
while( l<r )
{
int mid = l + r + 1 >> 1;
if( dp[mid]<a[i] ) l = mid;
else r = mid - 1;
}
len = max( len, r + 1);
dp[r+1] = a[i]; //更新dp[]
}
cout << len << endl;
return 0;
}
C++代码 2
找最大的[HTML_REMOVED]=ai的 可以用lower_bound实现
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 2e9;
const int Max_N = 1e5+10;
int n;
int a[Max_N];
int dp[Max_N]; //dp[i] 长度为i符合贪心思想的上升子序列(末尾值最小)
int main()
{
cin >> n;
for( int i=0; i<n; i++ ) cin >> a[i];
int res = 0; //dp[]长度
fill( dp, dp+n, INF); //将dp赋值为INF 使得每个ai都有>=INF的下标
for( int i=0; i<n; i++ )
{
int j = lower_bound(dp,dp+n, a[i]) - dp; //返回更新下标
dp[j] = a[i];
res = max( res, j );
}
cout << res+1 << endl; //长度 = 最大下标+1
return 0;
}