LeetCode673. Number of Longest Increasing Subsequence

冷不防 2022-06-07 00:58 142阅读 0赞

A naïve approach of this question would be to generate all the sequences along the way we iterating each number in the input `nums`. And each time for a new number, we iterate through all previous generated sequences and try to get new ones. Finally we count all the sequences with the longest length. Generating all combinations could take `O(2^n)` time in the worst case where `n` is the length of the input array.

However, in this question, we don’t care about the real sequence or the position of the sequence, we only care about how many of longest increasing sequences are there. Thus storing all sequences is redundant work. Considering that to determine a increasing sequence, we actually only need the last one number of the sequence, we can just keep that number of each position of `nums`, as long as the length of current sequence (used for determine longest sequence) and count (number of sequences of this length for this position).

Hence, for each new number we encountered, we traverse the previous positions’ results and try to construct new increasing sequences based on their ending number. At the same time we change the current length of count correspondingly. **However, the ending number of each position is always the current number. So we don’t even have to store this number.**

This will take `O(n^2)` time, `O(n)` space where `n` is the length of the input array.

Java implementation is showed as following:

class Solution {
        
        public int findNumberOfLIS(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
    
            int[][] cache = new int[nums.length][3]; //[index][end, len, count]
            int maxLen = 0;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                int[] tmp = new int[]{nums[i], 1, 1};
                for (int j = 0; j < i; j++) {
                    if (cache[j][0] < nums[i] && cache[j][1] + 1 == tmp[1]) {
                        tmp[2] += cache[j][2];
                    } else if (cache[j][0] < nums[i] && cache[j][1] + 1 > tmp[1]) {
                        tmp[1] = cache[j][1] + 1;
                        tmp[2] = cache[j][2];
                    }
                }
    
                cache[i] = tmp;
    
                if (maxLen == tmp[1]) {
                    count += tmp[2];
                } else if (maxLen < tmp[1]) {
                    count = tmp[2];
                    maxLen = tmp[1];
                }
            }
    
            return count;
        }
    }