原题地址

https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/

题目描述

给定一个无序的数组，找出这个数组中包含的最长递增子序列的数目。（不是求最长递增子序列的长度，是问有几个最长递增子序列）

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

思路

n为给定数组长度，L[ i ]表示以第i个(0<=i<=n-1)元素结尾的递增子序列能达到的长度，用动态规划的方法求出所有L[ i ]，找出其中的最大值longest。
如果longest=1，说明每个单独的元素都是一个最长递增子序列，数组中所有元素都递减或者相等，此时直接返回数组长度n即可。
count[ i ]表示到达第i个元素且长度为L[ i ]的子序列的数目，初始全为0，i=1到n，每次扫描第i个元素之前的所有元素j，若元素j < 元素i，且L[ j ]+1=L[ i ]，就增加count[ i ]的值：若count[ j ] 不为0，则加上count[ j ]的值；若count[ j ]=0则加1。
最后遍历求出的count数组，将L[ i ]=longest 的元素 i 对应的count[ i ]求和就是最后结果。
复杂度为 O(n^2)

代码

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        int L[n],count[n];
        int longest = 0;
        int result = 0;
        for (int j = 0; j < n; j++) {
            L[j] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && L[i] <= L[j] + 1) {
                    L[i] = L[j] + 1;
                }
            }
            if (longest < L[i]) {
                longest = L[i];
            }
        }

        if (longest == 1) {
            result = nums.size();
        } else {
            memset(count, 0, sizeof(L[0])*n);
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j] && L[i] == L[j] + 1 ) {
                        if (count[j] == 0) {
                            count[i] += 1;
                        } else {
                            count[i] += count[j];
                        }
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                if (L[i] == longest) {
                    result += count[i];
                }
            }
        }
        return result;
    }
};