673. Number of Longest Increasing Subsequence (Medium)

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Solution 1: DP O(n^2); O(1)

The idea is to use two arrayslen[n]andcnt[n]to record the maximum length of Increasing Subsequence and the coresponding number of these sequence which ends withnums[i], respectively. That is:

len[i]: the length of the Longest Increasing Subsequence which ends withnums[i].
cnt[i]: the number of the Longest Increasing Subsequence which ends withnums[i].

Then, the result is the sum of eachcnt[i]while its correspondinglen[i]is the maximum length.

len[i] == len[j] + 1 means that you find another subsequence with the same length of LIS which ends with nums[i]. While len[i] > len[j] + 1 means that you find a subsequence, but its length is smaller compared to LIS which ends with nums[i].

    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //state
        int[] f = new int[nums.length]; //用来记录第i个位置的最长长度
        int[] ans = new int[nums.length]; //用来记录第i个位置的最长的个数
        //init
        f[0] = 1;
        ans[0] = 1;
        //func
        int max_len = 1;
        for (int i = 1; i < nums.length; ++i) {
            //init 
            f[i] = 1;
            ans[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i] && f[j] + 1 > f[i]) {
                    //一个新的子序列
                    f[i] = f[j] + 1;
                    ans[i] = ans[j];
                } else if (nums[j] < nums[i] && f[j] + 1 == f[i]) {
                    ans[i] += ans[j];
                }
            }
            max_len = Math.max(f[i], max_len);
        }
        //ans
        int res = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (max_len == f[i]) {
                res += ans[i];
            }
        }
        return res;
    }

另一种写法，计数放在for循环里面

    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, res = 0, max_len = 0;
        int[] len =  new int[n], cnt = new int[n];
        for(int i = 0; i<n; i++){
            len[i] = cnt[i] = 1;
            for(int j = 0; j <i ; j++){
                if(nums[i] > nums[j]){
                    if(len[i] == len[j] + 1)cnt[i] += cnt[j];
                    if(len[i] < len[j] + 1){
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    }
                }
            }
            if(max_len == len[i])res += cnt[i];
            if(max_len < len[i]){
                max_len = len[i];
                res = cnt[i];
            }
        }
        return res;
    }

Follow Up:

1.求LIS的长度

    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int[] lis = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            lis[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i])//符合计数条件
                    lis[i] = Math.max(lis[j] + 1, lis[i]);//只有当lis[j] + 1比当前lis[i]大才更新
            }
        }
        int max_len = 0;
        for(int num: lis){
            max_len = Math.max(num, max_len);
        }
        return max_len;
    }