LIS

LISとはLongest Increase Subsequence の略で最長増加部分列と呼ばれる問題です。増加部分列とはすべての i < j で a_i < a_j となっている部分列のことです。

簡単な例を見てみます。

a_n = {1,3,5,2,4,6} という数列 a_n を考えます。この時の最長増加部分列の長さは 4 (1,3,4,6),(1,2,4,6) です。

この問題はDPで O(N logN) で解けます。考え方は、同じ長さの増加部分列であれば最終要素が小さいほうがその後に有利です。例えば長さ4の2つの増加部分列があるとして、b_n={100,200,300,400}とc_n={1,200,300,400}であれば、c_nのほうが最終要素が1なので、その後増加部分列として追加できる要素の候補がb_nよりも多く有利ということです。よって長さに対して最小の最終要素を求めることで、INFでない最大のindexを求めよう。という考え方です。

dp[i]:=長さがi+1であるような増加部分列における最終要素の最小値（存在しない場合はINF）とします。

この長さnの配列を更新していきます。

0.各配列をINFで初期化

i	0	1	2	3	4	5	6
dp[i]	INF	INF	INF	INF	INF	INF	INF

1.1を挿入

i	0	1	2	3	4	5	6
dp[i]	1	INF	INF	INF	INF	INF	INF

2.3を挿入

i	0	1	2	3	4	5	6
dp[i]	1	3	INF	INF	INF	INF	INF

3.5を挿入

i	0	1	2	3	4	5	6
dp[i]	1	3	5	INF	INF	INF	INF

4.2を挿入

i	0	1	2	3	4	5	6
dp[i]	1	2	5	INF	INF	INF	INF

5.4を挿入

i	0	1	2	3	4	5	6
dp[i]	1	2	4	INF	INF	INF	INF

6.6を挿入

i	0	1	2	3	4	5	6
dp[i]	1	2	4	6	INF	INF	INF

上記の更新結果を確認するとINFでない最大のindexは4であることがわかります。よってこの数列a_nのLISの長さは4です。

Javaでの具体的な実装例は以下になります。これは計算量O(N²)です。

public class Sample {

    public static final int INF = 1 << 30;
    
    public static void main(String[] args) {

        int[] a = {1, 3, 5, 2, 4, 6};
        int len = a.length;
        int[] dp = new int[len+1];
        Arrays.fill(dp, INF);

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (dp[j] > a[i]) {
                    dp[j] = a[i];
                    break;
                }
            }
        }

        // INFでない最大のiを求める
        int ans = -1;
        for (int i = 0; i < len; i++) {
            if (dp[i] == INF) {
                ans = i;
                break;
            }
        }
        System.out.println(ans);

    }
}

上記の実装を高速化しましょう。dp[i]をa_jで更新する際に上記の実装ではforループで小さい要素から順番に参照し、更新するindexを求めていました。ここでdp[i]は狭義単調増加列になっているため、二分探索で更新するindexを求めることができます。実装例は以下のようになります。計算量O(N logN)です。

public class Sample {

    public static final int INF = 1 << 30;

    public static void main(String[] args) {

        int[] a = {1, 3, 5, 2, 4, 6};
        int len = a.length;
        int[] dp = new int[len+1];
        Arrays.fill(dp, INF);

        for (int i = 0; i < len; i++) {
            int idx = lowerBound(dp, a[i]);
            dp[idx] = a[i];
        }

        // INFでない最大のiを求める
        int ans = lowerBound(dp, INF);
        System.out.println(ans);

    }

    public static int lowerBound(int[] a, int obj) {
        int l = 0, r = a.length - 1;
        while (r - l >= 0) {
            int c = (l + r) / 2;
            if (obj <= a[c]) {
                r = c - 1;
            } else {
                l = c + 1;
            }
        }
        return l;
    }
}

数学/競プロメモ

LISとは

LIS

練習問題