1. 首页
  2. 模板

最长上升子序列 模板

int a[M],b[M];
int search(int num,int low,int high)
{
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(num>=b[mid])
            low=mid+1;
        else
            high=mid-1;
    }
    return low;

}

int DP(int n)
{
    int i,len,pos;
    b[1]=a[1];
    len=1;
    for(int i=2; i<=n; ++i)
    {
        if(a[i]>b[len])   //如果a[i]比b[]数组中最大还大直接插入到后面即可
        {
            len=len+1;
            b[len]=a[i];
            vis[i]=1;
        }
        else              //用二分的方法在b[]数组中找出第一个比a[i]大的位
        {
            //并且让a[i]大的位置并且让a[i]替代这个位置
            pos=search(a[i],1,len);
            b[pos]=a[i];
        }

    }

    return len;

}

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/648 (转载时请注明本文出处及文章链接)
  • 本文无相关文章
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40