最長上昇サブシーケンスO(n^2)アルゴリズムとO(nlogn)アルゴリズム

4215 ワード

最長上昇サブシーケンス問題(LIS問題)

O(n^2)アルゴリズム(DP)
解析:1つの数列の最長上昇サブシーケンスについて,a[i]で終わるサブシーケンスの最長上昇シーケンスを1つの配列dp[i]で記録すると,容易に考えられる.
最初の要素にとって、彼のdp[1]=1;
後続の各要素iについて、彼のdp[i]は、前のdp[]の中で最大であるべきであり、次いで、dp[i]=max(dp[j])(j from 1 to i)を加えなければならない.
以上の解析から,1つの数列a[]に対して,a[i]で終わるシーケンスの最長上位昇子シーケンスをdp[i]で表すと,i以前の
0<=j

int solve(int a[],int n)  
{  
    int ans=-1;   
    for(int i=0;i<n;i++)  
        dp[i]=1;  
    for(int i=0;i<n;i++)  
    {  
        for(int j=0;j<i;j++)  
        {  
            if(a[i]>a[j])  
                dp[i]=max(dp[i],dp[j]+1); //              ，   dp[j]+a[i] 
        }  
        ans=max(ans,dp[i]);  
    }  
    return ans;  
}

1つの数列で分割できる最長の上昇しないサブシーケンスの個数を求めると、Dilworthの定理から分かる.
1つの数列の最長上昇しないサブシーケンスの数は、その数列の最長上昇サブシーケンスの長さに等しい.
Dilworthの定理:
定理1)命令(X,≤)は有限バイアスセットであり,rはその最大鎖の大きさである.Xはr個に分けることができるが、これ以上少ない反鎖はできない.
定理2)命令(X,≤)は有限バイアスセットであり,mは反鎖の最大サイズである.Xはm個に分けられるが、これ以上少なくはならない鎖に分けられる.
例えばHDU 1257最小ブロックシステム

#include <cstdio>
#include <algorithm>
#define MAX 1000
using namespace std;
int main()
{
    int n,i,j,ans;
    int a[MAX],dp[MAX];
    while(scanf("%d",&n)!=-1)
    {
        ans=0;
        for(i=0;i<n;i++)
          scanf("%d",&a[i]);
        for(i=0;i<n;i++)  dp[i]=1;
        for(i=0;i<n;i++)
        {
            for(j=0;j<=i;j++)
            {
                if(a[i]>a[j])
                  dp[i]=max(dp[i],dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}

もう1つはO(nlogn)のアルゴリズムです
厳密に言えば、このアルゴリズムは二分に属するべきで、DPとはあまり関係がありません.大体このようなものです.
長さiのこの分子配列のうち、ans[]の最小値、すなわちstack[i]=min(a[])(a[]は長さiのすべてのサブ配列の末尾要素からなる配列である)を表す配列stack[i]を定義する.
stack[]があれば、この配列を利用してこの配列の最も長い上昇サブシーケンスを見つけることができ、まずlenをこのシーケンスの最大上昇サブシーケンスとして定義し、len=1;
(1)配列の第1項についてはans[0]で初期化でき,stack[len]=ans[0];
(2)後の各ans[i](i from 1 to n-1)について,forループで遍歴する.
(a)ans[i]>stack[len]の場合、その要素をlenシーケンスに追加し、シーケンス長を更新します:stack[++len]=ans[i];
(b)ans[i]<=stack[len]の場合、ans[i]>stack[j]に1からlenの最大のjを見つけ、stack[j]=ans[i];
これで最終的なlen値が得られ、出力すればよい.
実はこのアルゴリズムもO(n^2)で、ansとstackの2割が遍歴しているので、しかしこのような事実があって、あなたが得たstack配列はずっと単調で非漸減で、それではこの時遍歴は2分で、それによってアルゴリズム全体をO(nlogn)に下げることができます.
例えばPOJ 2533 Longest Ordered Subsequence
長さnのシーケンスを与えて、そのLISの長さを求めます.

#include <cstdio>
#include <iostream>
#define MAX 100005
using namespace std;
int ans[MAX],stack[MAX];
int LIS(int temp,int len)
{
    int left=0,right=len;
    int mid=(left+right)/2;
    while(left<=right)
    {
        if(temp>stack[mid])  left=mid+1;
        else right=mid-1;
        mid=(left+right)/2;
    }
    return left;
}
int main()
{
    int n,temp,len;
    while(scanf("%d",&n)!=-1)
    {
        for(int i=0;i<n;i++)
          scanf("%d",&ans[i]);
        len=1;
        stack[len]=ans[0];
        for(int i=1;i<n;i++)
        {
            if(ans[i]>stack[len])
              stack[++len]=ans[i];
            else
            {
                int j=LIS(ans[i],len);
                stack[j]=ans[i];
            }
        }
        printf("%d
",len);
    }
    return 0;
}

lowerでbound()で実装されるコードは次のとおりです.

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 100005
#define inf 0x3f3f3f3f
int dp[maxn];
int a[maxn];
int n;
void solve(){//        （LIS）（nlogn）
    fill(dp,dp+n,inf);//fill      0~n         
    for(int i=0;i<n;i++)
    {
        *lower_bound(dp,dp+n,a[i])=a[i];
        //          ，                     ，
        //        dp                     。
    }
    printf("%d
",lower_bound(dp,dp+n,inf)-dp);
}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        solve();
    }
    return 0;
}

ビットマップアルゴリズムのユーザー検証への応用

Kruskal(クルースカル)最小生成ツリーアルゴリズム詳細+テンプレート