关于最长上升子序列的一个程序的疑惑,希望大佬帮忙解惑一下
  • 板块学术版
  • 楼主HXR123
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/4 14:05
  • 上次更新2023/11/3 11:39:37
查看原帖
关于最长上升子序列的一个程序的疑惑,希望大佬帮忙解惑一下
393699
HXR123楼主2023/7/4 14:05

程序的第十行:(f[i]=0x7fffffff;)将f[i]赋值为最大值对整个程序有什么作用?有哪位大佬可以帮忙解惑一下吗?原题

#include<iostream>
#include<cstdio>
using namespace std;
int a[100001],b[100001],map[100001],f[100001];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){scanf("%d",&a[i]);map[a[i]]=i;}
	for(int i=1;i<=n;i++){scanf("%d",&b[i]);f[i]=0x7fffffff;}
	int len=0;
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		int l=0,r=len,mid;
		if(map[b[i]]>f[len])f[++len]=map[b[i]];
		else 
		{
		while(l<r)
		{	
		    mid=(l+r)/2;
		    if(f[mid]>map[b[i]])r=mid;
			else l=mid+1; 
		}
		f[l]=min(map[b[i]],f[l]);
     	}
    }
    cout<<len;
    return 0
}
2023/7/4 14:05
加载中...