【C】最長増分子列(LIS)解

以下に述べるサブストリング/サブストリングには異なる理解があるかもしれないが、ネット上のほとんどの人はSubsequenceをサブストリング、Substringをサブストリングと考えているため、以下の内容はサブストリングであり、本明細書に曖昧さが生じたり、私が書き間違えたりした場合、以上の2つの語を一律にSubsequence LIS(Longest Increasing Subsequence)最長増分サブシーケンス問題と見なすのは非常に基礎的なDP問題であり,ここでは主にDP問題を解決する最も重要な方法の一つである記憶化検索について説明するためであり,ここでは複雑度Oのみを説明する(N 2)の方法でこの問題を解決し,ここでは長男シーケンス長を求めるだけで,具体的にどのサブシーケンスであるかについても議論せず,最後にO(Nlogn)の問題解決コードを添付するが,あまり説明しない.
まず定義を明らかにしましょう
サブシーケンスとは?
元の列から一部のデータを削除し、残りのデータを元の順序で並べた列をその列のサブシーケンスと呼ぶ.例えば、1、2、3、4、5、6、7、8、9の列について、1、2、3はそのサブシーケンスであり、1、3、9はそのサブシーケンスであり、1、2、3、4、5、6、7、8、9もそのサブシーケンスである(サブシーケンスはそれ自体であってもよい)が、例えば1、4、3または1、3、3または1、9、2、3、4、5、6、7、8はいずれもその列のサブシーケンスではない.
増分サブシーケンスとは?
これはよく理解されています.すなわち、このサブシーケンスは順番に増加します.上記の例では、そのすべてのサブシーケンスはインクリメントされます(この列自体がインクリメントされた列であるため、そのすべてのサブシーケンスはインクリメントされます).
一番長いのは何ですか.
これは説明するまでもないでしょうが、上記の例では、それ自体が最長男シーケンスです
以下の議論の過程で,1,7,3,4,5,9,8,9という列を用いたが,ここで最も長い増分サブシーケンスは1,3,4,5,8,9である
問題を分析する
1、この列が最初のデータ(すなわち1のみ)しかないと仮定すると、最上位シーケンスの長さは1であると判断できます.2、このとき、2番目のデータを追加します.(すなわち1,7)我々は,7>1,すなわち,この答えに加えることができる,すなわち,最長男シーケンス長が2 3である,このとき我々は3番目のデータを加える--3,3を最長列に加えるには,7を捨てて1,3列を構成しなければならないという問題を発見した.(1、7または1、3)は、長さが2のサブシーケンスです.この長さが2の場合、どのように判断されますか.この人間の脳の不思議な思考過程をコンピュータ言語でどのように解釈するかをよく考えなければなりません.1の前にn個のデータがあり、1がn+1番目の数、7がn+2、3がn+3と仮定することができます.この場合、私たちの前にこのようにして、3の前の数すでに多くの増分列が構成されているが、3が前の「大家族」に加わる必要がある場合は、最後尾のデータが3未満の列を見つける必要がある.では、3にとって最も優れた列(すなわち、最も長い列)を見つけるには、3に加えられるすべての列の中で、最も長い列を見つける必要があります.(追加可能な列がなければ、長さは1)前の各データ/要素を1つの列に書くことができます.すなわち、このデータを考慮した後、このデータを満たす最適な列を保存し、次のデータをこれらの列の中に最適なものを探して、この新しいデータに新しい列を添付します.例えば、次のデータ:4、その前に、1と1、7と1、3の3つの列がありました.(1番目の列は1つのデータ1しかない.1にとって、前には列がないので、自分で列を作っているが、他の2つのデータについては、単独の列がない.理由:例えば、7、あるデータが7という列の末尾に加わることができれば、必ず1、7という列の末尾を加えることができる.)では、4は列が1または1、3であることが明らかである.1、3という列に加え、1、3、4という列を作り、保存します.このようにすれば、以下の表が得られる.
例
1
7
3
4
5
9
8
9
このデータに対応する最長列
1
1、7
1、3
1、3、4
1、3、4、5
1、3、4、5、9
1、3、4、5、8
1、3、4、5、8、9
ここでは,最後のデータと現在の長さの2つの列の唯一の意味のある2つのデータを比較する際に注意する.すなわち,我々が保存する際には,前に決定した列を無視し,最後のビットのサイズが現在の比較のパラメータより小さいかどうかを考慮するだけでよい.列を現在の数に保存しているので、この列の最後の数がこの数に等しい(上の表から分かるように、下の列の最後の値は必ず上のデータに等しい)場合、表は以下のように簡略化できます.
例
1
7
3
4
5
9
8
9
最も長い列の長さ
1
2
2
3
4
5
5
6
では、最後に最大のデータがいくらなのかを調べるだけです.ここではコードを直接与えます

#include

int main()
{
    int n,a[1005],i,j,f[1005],maxn;//f            
    maxn=0;
    scanf("%d",&n);//        
    for (i=0; i<n; i++)
    {
        scanf("%d",&a[i]);//   
    }
    for (i=0; i<n; i++)
    {
        f[i]=1;//       1
        for (j=i-1; j>=0; j--)
        {
            if (f[j]+1>f[i] && a[j]<a[i])//          +1      ，              
            {
                f[i]=f[j]+1;
            }
        }
    }
    for (i=0; i<n; i++)//    f     
    {
        maxn=maxn>f[i]?maxn:f[i];
    }
    printf("%d
",maxn);//  
    return 0;
}

ここでは、記憶化検索という重要なアイデアを使いました.すなわち、現在の判断の対象の前のデータを整理した上で重要なデータを保存して次の判断に用いる.
最後に、私はもう一つの理解が難しい方法を提供して、思想は依然として記憶化の検索で、しかし複雑度はO(Nlogn)だけあって、ここでこのコードに対して多すぎる解釈をしません.

#include

int maxn[1005],maxlen;

int finddate(int l,int r,int t)
{
    if (l==r)
    {
        return r;
    }
    int m=(l+r)/2;
    if (maxn[m]>t)
    {
        return finddate(l, m, t);
    }
    else
    {
        return finddate(m+1, r, t);
    }
}

int main()
{
    int n,a[1005],i;
    maxlen=1;
    scanf("%d",&n);
    for (i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    maxn[0]=a[0];
    for (i=1; i<n; i++)
    {
        if (maxn[maxlen-1]<a[i])
        {
            maxn[maxlen]=a[i];
            maxlen++;
        }
        else
        {
            maxn[finddate(0,maxlen-1,a[i])]=a[i];
        }
    }
    printf("%d
",maxlen);
    return 0;
}