673 Number of Longest Increasing Subsequence

673. Number of Longest Increasing Subsequence

1. Question

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.

2. Implementation

(1) DP

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        // len[i] is the length of longest subsequence that end with nums[i]
        int[] len = new int[n];
        // count[i] is the number of longest subsequence that end with nums[i]
        int[] count = new int[n];

        Arrays.fill(len, 1);
        Arrays.fill(count, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    }
                    else if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
        }

        int maxLen = 1;
        for (int l : len) {
            maxLen = Math.max(maxLen, l);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (maxLen == len[i]) {
                res += count[i];
            }
        }
        return res;
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(n^2), 空间复杂度O(n)