欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长上升子序列

程序员文章站 2024-03-03 18:24:52
...

动态规划算法

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int f[1007];
int a[1007];
int main()
{
     int n;
     cin>>n;
     for(int i=1;i<=n;i++)
     {
         cin>>a[i];
         f[i]=1;
     } 
     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 ans=-10;
     for(int i=1;i<=n;i++)
     {
    	ans=max(ans,f[i]);
     }
     printf("%d",ans);
	 return 0;
} 

树状数组维护算法

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=103,inf=0x7f7f7f7f;
struct Node{
	int val,num;
}z[maxn];
int T[maxn];//下标是数组里的值 
int n,ans;
bool cmp(Node a,Node b)
{
	if(a.val==b.val)
	{
		return a.num<b.num;
	}
	else
	{
		return a.val<b.val;//升序排序 
	}
	//return a.val==b.val?a.num<b.num:a.val<b.val;
}
void modify(int x,int y)
{
	for(;x<=n;x+=x&(-x)) T[x]=max(T[x],y);
}
int query(int x)//树状数组向下查询函数 
{
	int res=-inf;//res的值是无穷小 
	for(;x;x-=x&(-x)) res=max(res,T[x]);//返回值为x转换为二进制,将最后一个1进位的结果 
	return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	cin>>z[i].val;//val保存数值 
    	z[i].num=i;//num保存下标 
    }
    sort(z+1,z+n+1,cmp);//结构体排序,按val优先排序
    for(int i=1;i<=n;i++)
    {
    	int maxx=query(z[i].num);
    	modify(z[i].num,++maxx);
    	ans=max(ans,maxx);
    }
    cout<<ans;
    return 0;
}
相关标签: 模板题