673. Number of Longest Increasing Subsequence

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.

用兩個1D array紀錄長度和數量。len[i]代表以nums[i]結尾的LIS長度，cnt[i]代表以nums[i]結尾的LIS數量。初始化的值為1，因為只要數列有數字，至少都有1個長度為1的LIS。

int findNumberOfLIS(vector<int>& nums) { // time: O(n^2); space: O(n)
    int n = nums.size(), res = 0, maxLen = 0; // initialize to 0 for empty input
    vector<int> len(n, 1), cnt(n, 1);
    // len[i]: the length of LIS ending with nums[i]
    // cnt[i]: the number of LIS with len[i]
    // DP relation: len[i] = max({len[j]}, 0 <= j < i) + 1
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (len[i] == len[j] + 1)
                    cnt[i] += cnt[j];
                else if (len[i] < len[j] + 1) {
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                }
            }
        }
        if (maxLen == len[i]) res += cnt[i];
        else if (maxLen < len[i]) {
            maxLen = len[i];
            res = cnt[i];
        }
    }
    return res;
}

300. Longest Increasing Subsequence674. Longest Continuous Increasing Subsequence