LeetCoding Challenge Oct.30: # of Longest Increasing Subseq

LeetCode October Challenge の 30 日目。

今日の問題は Number of Longest Increasing Subsequence。

問題の概要

• 与えられた配列に含まれる最長増加部分列の本数を求める
• 例) [1,3,5,4,7] であれば、[1,3,4,7] と [1,3,5,7] の 2 本 となる

考え方

• これは難しい (というか苦手) ですね… 😫
• 問題の解き方について考えてみる
  • 配列上のある数値 nums[i] に着目する
  • nums[i] が増加部分列の末尾となるケースを想像してみる
    • 配列の 0 .. i-1 の間に存在する増加部分列のうち、その末尾が nums[i] に 満たない 増加部分列の末尾に nums[i] は加わることができる
    • そして、その増加部分列の長さは +1 される
  • 今回の問題では最長の増加部分列の本数を求めることになるので、「増加部分列の長さ」だけではなくてその長さの増加部分列の「本数（個数）」も考えねばならない…
• ちょっと妙案が浮かばないので、まずナイーブに時間計算量 O(n^2) かかるアルゴリズムでいいので考えてみよう
  • 実装してみた (詳細は コード上のコメント を参照)
• submit → accept 😊
  • しかし runtime 14ms で Your runtime beats 54.93 % of java submissions. かあ…
• もうちょっと賢くできないものか？ 🤔
  • 実装してみた (こちらも詳細はコード上のコメント を参照)
• submit → accept 👍
  • 今回は runtime 5ms で Your runtime beats 99.43 % of java submissions.
  • このあたりが限界かな…

コード

ナイーブなアルゴリズム

class Solution1 {
    public int findNumberOfLIS(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }

        // i の位置において、nums[i] の値を増加部分列の末尾とするような増加部分列の
        // 「長さ」とその「本数」を以下の配列で保持する。

        int[] lengths = new int[nums.length];
        int[] counts = new int[nums.length];
        lengths[0] = 1;
        counts[0] = 1;

        for (int i = 1; i < nums.length; i++) {
            int maxLen = Integer.MIN_VALUE;
            int totalCount = Integer.MIN_VALUE;

            // i - 1 以前より、増加部分列の末尾が nums[i] より小さくてかつ最も長い
            // 増加部分列の本数を数えて lengths/counts を順次更新していく。

            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    if (lengths[j] > maxLen) {
                        maxLen = lengths[j];
                        totalCount = counts[j];

                    } else if (lengths[j] == maxLen) {
                        totalCount += counts[j];
                    }
                }
            }

            if (maxLen > 0) {
                lengths[i] = maxLen + 1;
                counts[i] = totalCount;
            } else {
                // nums[i] より小さい値が見つからなければ、自身だけで構成される
                // 増加部分列が存在することを意味する。
                lengths[i] = 1;
                counts[i] = 1;
            }
        }

        // 全体を通して、最長となる増加部分列の本数を数え上げて解とする

        int maxLen = 1;
        int totalCount = 1;
        for (int i = 1; i < lengths.length; i++) {
            if (lengths[i] > maxLen) {
                maxLen = lengths[i];
                totalCount = counts[i];
            } else if (lengths[i] == maxLen) {
                totalCount += counts[i];
            }
        }

        return totalCount;
    }
}

ちょっと賢いアルゴリズム

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }

        // 配列を左から右に走査していく過程において、最終的な解になりうる増加部分列を
        // その末尾の値 (増加部分列中の最大値) で束ねることにする。

        // そして、この束ねられた増加部分列をさらに増加部分列の長さごとにグループ化して、
        // 以下の groupByLen で管理する。

        // groupByLen の要素が一つのグループを表し、groupByLen の添字はそのグループの
        // 増加部分列の長さ - 1 を表している。

        // グループの中は増加部分列末尾の値の昇順にソートされていて、それぞれの要素 (long 値) の
        // 上位 32 ビットが増加部分列末尾の値を表している。
        // そして下位 32 ビットが、(増加部分列の長さと) 増加部分列末尾の値が等しい
        // 増加部分列の本数を表している。

        List<List<Long>> groupByLen = new ArrayList<>();
        groupByLen.add(new ArrayList<>());
        groupByLen.get(0).add(((long) nums[0] << 32) | 1);

        for (int i = 1; i < nums.length; i++) {
            long searchKey = (long) nums[i] << 32;
            long count = 1;
            List<Long> listToAdd = groupByLen.get(0);

            for (int j = groupByLen.size() - 1; j >= 0; j--) {
                // これまでに見てきた増加部分列の中から、その末尾の値が現在着目している数値 (nums[i]) より小さく、
                // かつ最長である加部分列の束を探し出したい。

                // このとき、グループ化して管理している groupByLen のリストの末尾から探索することで
                // 目的のものを容易に見つけることができる。

                List<Long> list = groupByLen.get(j);
                if (list.get(0) > searchKey) {
                    continue;
                }

                // 目的の増加部分列を含んだグループが特定できたところで、そのグループに含まれる増加部分列の束のうち
                // 着目している数値より小さいものすべての本数を数え上げる。

                count = 0;
                for (long v : list) {
                    long num = v >> 32;
                    if (num >= nums[i]) {
                        break;
                    }
                    count += v & 0x7fff_ffff;
                }

                int len = j + 1;
                if (len == groupByLen.size()) {
                    groupByLen.add(new ArrayList<>());
                }

                listToAdd = groupByLen.get(len);
                break;
            }

            // 今度は、着目している数値で終わる新たな増加部分列をグループに登録する。
            // どのグループに入れるべきかはすでに確定しているので、そのグループのどの位置
            // (リストのインデックス) に挿入すべきかを二分探索で見つける。

            int index = Collections.binarySearch(listToAdd, searchKey);
            if (index < 0) {
                index = -(index + 1);
            }

            if (index < listToAdd.size() && listToAdd.get(index) >> 32 == nums[i]) {
                // 仮に同グループにすでに着目している数値で終わる増加部分列の本数が記録されていたなら、
                // リストに要素を追加する必要はなく本数を書き換えるだけで済む。
                count += (listToAdd.get(index) & 0x7fff_ffff);
                listToAdd.set(index, searchKey | count);

            } else {
                // グループにまだ存在しない要素であれば、挿入位置に追加する。
                listToAdd.add(index, searchKey | count);
            }
        }

        // 配列を走査し終えれば、あとは増加部分列が最長であるグループの
        // 増加部分列の本数を足し合わせれば OK。
        long count = 0;
        for (long v : groupByLen.get(groupByLen.size() - 1)) {
            count += v & 0x7fff_ffff;
        }

        return (int) count;
    }
}