LeetCoding Challenge Oct.30: # of Longest Increasing Subseq

문제의 개요

생각

코드

순산법

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;
    }
}