LIS (Longest Increasing Subsequence) とは最長単調増加シーケンスのこと。数字列(あるいは文字列等、互いに大きさの比較ができるものなら何でもOK)の中から、値が大きくなっていき、もっとも長いシーケンス(数字列)を見つけ出すアルゴリズムのことです.

 -7, 10, 9, 2, 3, 8, 1

例えば,上の数字列では,LIS は -7 2 3 8 になり、その長さは4だ。

また、概念は同じだが、LDS (Longest Decreasing Subsequence、最長単調減少シーケンス) というのもある。

ここでは、i (1<=i<=N、Nはシーケンスの長さ)番目から始まるLIS(またはLDS)の長さについて考える。

上の例では、LIS[i] = { 4, 1, 1, 3, 2, 1, 1 }
      LDS[i] = { 1, 3, 2, 2, 2, 1, 1 } となる。

各データの位置から、LIS(LDS)の長さが分かれば、LISシーケンスを作り出すことができる。

#define SIZE 10000 /* 必要に応じて変更 */
int N; /* データの個数 */
int num[SIZE+3]; /* データ */
int LIS[SIZE+3]; /* LIS長さ */
int LDS[SIZE+3]; /* LDS長さ */
void calc(void)
{
    int i, j;
    int mi, md;
    LIS[N-1] = LDS[N-1] = 1;
    for (i = N-2; i >= 0; i--) {
        mi = md = 0;
        for (j = i+1; j < N; j++) {
            if (num[i] < num[j]) {
                if (LIS[j] > mi) mi = LIS[j];
            } else {
                if (LDS[j] > md) md = LDS[j];
            }
        }
        LIS[i] = mi+1;
        LDS[i] = md+1;
    }
}

計算時間は O(N^2) 。

下のコードはO(nlogn)の高速バージョン。LISのみになっているが、LDSへの対応もそれほど困難ではないだろう。

#define SIZE 10005  /* 配列のサイズ。適宜変更 */
int N;  /* データの個数 */
int max;  /* 計算終了の時点では最長LISの値が入る */
int num[SIZE+3];  /* データ */
int LIS[SIZE+3];  /* それぞれのデータ置からのLIS長さ */
int tmp[SIZE+3];  /* 作業用 */
void calc(void)
{
    int k;
    int lo, hi, mid;
    LIS[N-1] = 1;
    tmp[0] = num[N-1];
    max = 1;
    for (k = N-2; k >= 0; k--) {
        if (tmp[max-1] > num[k]) { tmp[max++] = num[k]; LIS[k] = max; continue; }
        if (tmp[max-1] == num[k]) { LIS[k] = max; continue; }
        lo = 0;
        hi = max;
        while (lo < hi) {
            mid = (lo + hi) >> 1;
            if (tmp[mid] > num[k]) lo = mid+1;
            else hi = mid;
        }
#if 0
        if (lo < max) tmp[lo] = num[k], LIS[k] = lo+1;
        else tmp[max++] = num[k], LIS[k] = max;
#else
        tmp[lo] = num[k], LIS[k] = lo+1;
#endif
    }
}

Comments are closed.

Post Navigation