673. Number of Longest Increasing Subsequence

二刷 07/2022

Version #2 DP + binary search + prefix sum

比想象中的好写一点，关键点是binary search到start == end的时候，start点不一定是符合条件的，需要特殊讨论

另一个很大的bug是Arrays.fill(endings, new ArrayList<>())会造成所有的index都是同一个list，不能这么写

Time O(NlogN)

Space O(N)

Runtime: 10 ms, faster than 99.39% of Java online submissions for Number of Longest Increasing Subsequence.

Memory Usage: 47.1 MB, less than 5.28% of Java online submissions for Number of Longest Increasing Subsequence.

class Solution {
    public int findNumberOfLIS(int[] nums) {
        List<Pair<Integer, Integer>>[] endings = new ArrayList[nums.length];
        for (int i = 0; i < endings.length; i++) {
            endings[i] = new ArrayList<>();
        }
        // find the first index of the list whose last element is larger than or equals to nums[i]
        for (int num : nums) {
            int listIndex = findListIndex(endings, num);
            List<Pair<Integer, Integer>> list = endings[listIndex];
            int prevCount = 1;
            if (listIndex > 0) {
                List<Pair<Integer, Integer>> prevList = endings[listIndex - 1];
                prevCount = findPrevCount(prevList, num);
            }
            int prefixSum = 0;
            if (list.size() > 0) {
                prefixSum = list.get(list.size() - 1).getValue();
            }
            list.add(new Pair<>(num, prefixSum + prevCount));
        }
        for (int i = endings.length - 1; i >= 0; i--) {
            if (endings[i].size() > 0) {
                return endings[i].get(endings[i].size() - 1).getValue();
            }
        }
        return 0;
    }
    
    private int findPrevCount(List<Pair<Integer, Integer>> prevList, int num) {
        // prev list is a decreasing list
        // we need to find out the first index smaller than num
        int start = 0, end = prevList.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (prevList.get(mid).getKey() >= num) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        int total = prevList.get(prevList.size() - 1).getValue();
        if (start == 0 && prevList.get(start).getKey() < num) {
            return total;
        }
        return total - prevList.get(start - 1).getValue();
    }
    
    private int findListIndex(List<Pair<Integer, Integer>>[] endings, int num) {
        int start = 0, end = endings.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            List<Pair<Integer, Integer>> midList = endings[mid];
            if (midList.size() == 0) {
                end = mid;
                continue;
            }
            int lastElement = midList.get(midList.size() - 1).getKey();
            if (lastElement < num) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        if (endings[start].size() == 0 || endings[start].get(endings[start].size() - 1).getKey() >= num) {
            return start;
        }
        return start + 1;
    } 

} 

一刷 06/2022

Version #1 Naiive DP with two arrays

for each element in the array or on in the tree, they all carry three fields :

1) the maximum increasing / decreasing length ends at the current element,

2) its own value ,

3) the total number of maximum length,

Time O(N^2)

Space O(N)

Runtime: 33 ms, faster than 43.44% of Java online submissions for Number of Longest Increasing Subsequence.

Memory Usage: 44.3 MB, less than 53.55% of Java online submissions for Number of Longest Increasing Subsequence.

class Solution {

    public int findNumberOfLIS(int[] nums) {

        int[] len = new int[nums.length];

        int[] count = new int[nums.length];

        int maxLen = 0;

        int maxCount = 0;

        for (int end = 0; end < nums.length; end++) {

            len[end] = 1;

            count[end] = 1;

            for (int prev = end - 1; prev >= 0; prev--) {

                if (nums[prev] >= nums[end]) {

                    continue;

                }

                // nums[prev] < nums[end] - can concatenate

                if (len[prev] + 1 > len[end]) {

                    len[end] = len[prev] + 1;

                    count[end] = count[prev];

                } else if (len[prev] + 1 == len[end]) {

                    count[end] += count[prev];

                }

            }

            if (len[end] == maxLen) {

                maxCount += count[end];

            } else if (len[end] > maxLen) {

                maxLen = len[end];

                maxCount = count[end];

            }

        }

        return maxCount;

    }

}