【メモ】最長上昇サブシーケンス

列の数の最も長い上昇するサブシーケンスを求めます

O（n^2）

dp[i]をnum[i]で終わる最長上昇サブシーケンスの長さとして定義し、状態遷移方程式を書くのは難しくない.

dp[i]=max{dp[i],dp[j]+1} (num[j]<num[i] j<i)

できるはずだ.

O（nlogn）

上記の式を見ると,dp[i]は前i−1からdp値が最大のjを選択して更新され,nlognに最適化できることが分かる.
dp[i]を長さiの立ち上がりサブシーケンスの末尾要素の最小値とし、初期化dp値をINFとする.
これによりnum[i]をdp配列に更新し続けることができ,インクリメンタルであるため+O(1)修正を二分検索できる.
参考:『チャレンジプログラミングコンテスト』&&http://www.felix021.com/blog/read.php?1587
テーマ:codevs 3955
コード:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int size=1000010;
const int INF=233333333;

int num[size],dp[size];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        dp[i]=INF;
    }
    for(int i=1;i<=n;i++)
    {
        dp[lower_bound(dp+1,dp+1+n,num[i])-dp]=num[i];
    }
    printf("%d",lower_bound(dp+1,dp+1+n,INF)-dp-1);
    return 0;
}

次のように書くこともできます.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int size=1000010;
const int INF=233333333;

int num[size],dp[size];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        dp[i]=INF;
    }
    for(int i=1;i<=n;i++)
    {
        *lower_bound(dp+1,dp+1+n,num[i])=num[i];
    }
    printf("%d",lower_bound(dp+1,dp+1+n,INF)-dp-1);
    return 0;
}

参照を解除し、指定したアドレスに保存されている値を変更します.