原題地址

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

題目描述

給定一個無序的數(shù)組唧喉，找出這個數(shù)組中包含的最長遞增子序列的數(shù)目。（不是求最長遞增子序列的長度襟企，是問有幾個最長遞增子序列）

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為給定數(shù)組長度惨险，L[ i ]表示以第i個(0<=i<=n-1)元素結(jié)尾的遞增子序列能達(dá)到的長度胡嘿，用動態(tài)規(guī)劃的方法求出所有L[ i ]蝶柿，找出其中的最大值longest撰筷。
如果longest=1夏块，說明每個單獨的元素都是一個最長遞增子序列遥赚，數(shù)組中所有元素都遞減或者相等扬舒，此時直接返回數(shù)組長度n即可。
count[ i ]表示到達(dá)第i個元素且長度為L[ i ]的子序列的數(shù)目凫佛，初始全為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數(shù)組瞄勾，將L[ i ]=longest 的元素 i 對應(yīng)的count[ i ]求和就是最后結(jié)果费奸。
復(fù)雜度為 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;
    }
};