1.O(n²)算法
定义dp[i]:以ai为结尾的最长上升子序列的长度
以ai结尾的上升子序列是:
①只包含ai的子序列
②在满足j<i并且aj<ai的以aj为结尾的上升子列末尾,追加上ai后得到的子序列
综合以上两种情况,便可以得到递推关系式:
dp[i] = max{1, dp[j]+1| j<i且aj<ai}
2.O(nlogn)算法
定义dp[i]:长度为i+1的上升子序列中末尾元素的最小值(不存在就是INF)
最开始全部dp[i]的值都初始化为INF。然后由前到后逐个考虑数列的元素,对于每个aj,如果i=0或者dp[i-1]<aj的话,就用dp[i]=min(dp[i],aj)进行更新。最终找出使得dp[i]<INF的最大的i+1就是结果了。
STL二分查找
lower_bound():
头文件: #include<algorithm>
函数模板: 如 binary_search()
函数功能: 函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置
举例如下:
一个数组number序列为:4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标
则
pos = lower_bound( number, number + 8, 3) -number,pos = 0.即number数组的下标为0的位置。
pos = lower_bound( number, number + 8, 9) -number, pos = 1,即number数组的下标为1的位置(即10所在的位置)。
pos = lower_bound( number, number + 8, 111)- number, pos = 8,即number数组的下标为8的位置(但下标上限为7,所以返回最后一个元素的下一个元素)。
所以,要记住:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置,且last的位置是越界的!!~
返回查找元素的第一个可安插位置,也就是“元素值>=查找值”的第一个元素的位置
upper_bound():
头文件:#include<algorithm>
函数模板: 如binary_search()
函数功能:函数upper_bound()返回的在前闭后开区间查找的关键字的上界,返回大于val的第一个元素位置
例如:一个数组number序列1,2,2,4.upper_bound(2)后,返回的位置是3(下标)也就是4所在的位置,同样,如果插入元素大于数组中全部元素,返回的是last。(注意:数组下标越界)
返回查找元素的最后一个可安插位置,也就是“元素值>查找值”的第一个元素的位置
注意:
lower_bound(val):返回容器中第一个值【大于或等于】val的元素的iterator位置。
upper_bound(val): 返回容器中第一个值【大于】val的元素的iterator位置。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stack>
using namespace std;
const int MAX=1e6+10;int num[MAX];
int dp[MAX];int main(){int n;while(cin>>n){for(int i=0;i<n;i++)scanf("%d",&num[i]);int ans=0;for(int i=0;i<n;i++){dp[i]=1;for(int j=0;j<i;j++){if(num[i]>num[j])dp[i]=max(dp[i],dp[j]+1);}ans=max(ans,dp[i]);}cout<<ans<<endl;}return 0;
}
第二种:复杂度为O(nlogn)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int MAX=1e5+10;
int num[MAX] ;
int dp[MAX];
int main(){int n;while(cin>>n){int m,cnt;for(int i=0;i<n;i++)scanf("%d",&num[i]);fill(dp,dp+n,INF);for(int i=0;i<n;i++)*lower_bound(dp,dp+n,num[i])=num[i];cout<<lower_bound(dp,dp+n,INF)-dp<<endl;} return 0;
}