最长上升子序列 II
原题链接最长上升子序列 II.
基础知识介绍:
思路:贪心
:
这里的蕴含了一个贪心的思想,对于同样长度的子串,我当然希望它的末端越小越好
,这样以后我也有更多机会
拓展。(有一个很吊的名字dilworth
)(滑稽)
注意点:
因为最长上升子序列可能有好几个,而本解法是选择最平缓的,斜率最小的。
样例模拟:
例 n: 7
arr : 3 1 2 1 8 5 6
stk : 3
1 比 3 小
stk : 1
2 比 1 大
stk : 1 2
1 比 2 小
stk : 1 2
8 比 2 大
stk : 1 2 8
5 比 8 小
stk : 1 2 5
6 比 5 大
stk : 1 2 5 6
法一 $nlogn$
堆栈的方式 优化
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(void) {
int n; cin >> n;
vector<int>arr(n);
for (int i = 0; i < n; ++i)cin >> arr[i];
vector<int>stk;//模拟堆栈
stk.push_back(arr[0]);
for (int i = 1; i < n; ++i) {
if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈
stk.push_back(arr[i]);
else//(注意代替的是堆里面的那个第一个大于或者等于这个数字的那个数
//,比如如果堆里有 `1 3` 两个数 但是当遍历到的arr数组中的那个数是`2`时,就把`2`代替`3`
//,因此堆就变成 `1 2`)。
//这么做的原因就是前面所说的贪心思想。在最长子序列一定的时候都是长度为2,但是我们更希望末端是越小越好
//当然如果中间的数也希望在左右为止不变的情况下,依旧越小越好
*lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
}
cout << stk.size() << endl;
return 0;
}
法二nlogn
思路:二分查找
+ 贪心
这个方法思路和前面一样都是贪心
。只是实现方法不一样。用二分查找
写。二分查找模板–pcd推荐
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],q[N];
int main()
{
int n;
cin>>n;
int len=0;
for(int i=0;i<n;i++) cin>>a[i];
q[0]=-1e9;//这部分是二分模板,主要是找到那个数的下标
for(int i=0;i<n;i++)
{
int l=0, r=len;
while(l<r)
{
int mid=l+r>>1;
if(q[mid]>=a[i])r=mid;
else l=mid+1;
}
len=max(len,l+1);//如果l是返回最后一个数说明那个数比已有的上升子序列的最后的那个数要大
//得扩充长度了。
q[l]=a[i];//q数组老样子用来存上升序列
// cout<<l<<' ';
}
//cout<<endl;
// for(int i=1;i<n;i++)cout<<q[i]<<' ';
// cout<<endl;
cout<<len<<endl;
}
接下来的是最长上升子序列的长度
,不需要求出来最长子序列的具体为多少
原题链接最长上升子序列.
法三(dp
)经典做法,时间复杂度O n^2
f(i)表示从第一个数开始算,以第i个数结尾的最长上升子序列
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =1010;
int f[N];
int a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],f[i]=1;
//f[1]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
}
int res=0;
for(int i=0;i<=n;i++) res=max(res,f[i]);
cout<<res<<endl;
}
最长公共子序列
思路:贪心
如果两个字符相等,就可以直接转移到
f[i-1][j-1]
,不相等的话,两个字符一定有一个可以抛弃,可以对f[i-1][j],f[i][j-1]
两种状态取max
来转移。
主要难点,要清楚f[i][j]
表示第一个字符串取到下标为i
的字符,第二个字符串取到下标为j
的字符时,这之前最长的公共子序列长度
。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
char a[N],b[N];
int f[N][N];
int main()
{
int n,m;
cin>>n>>m;
cin>>a+1>>b+1;
for(int i = 1; i <= n;i ++)
for(int j = 1;j<=m;j++ )
{
f[i][j]=max(f[i-1][j],f[i][j-1]);//如果不相等就按照前面的
if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1] + 1);//相同就原基础加1
}
cout<<f[n][m]<<endl;
}