原題地址

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

題目描述

給定一個(gè)無(wú)序的數(shù)組，找出這個(gè)數(shù)組中包含的最長(zhǎng)遞增子序列的數(shù)目。（不是求最長(zhǎng)遞增子序列的長(zhǎng)度，是問(wèn)有幾個(gè)最長(zhǎng)遞增子序列）

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ù)組長(zhǎng)度，L[ i ]表示以第i個(gè)(0<=i<=n-1)元素結(jié)尾的遞增子序列能達(dá)到的長(zhǎng)度，用動(dòng)態(tài)規(guī)劃的方法求出所有L[ i ]，找出其中的最大值longest。
如果longest=1，說(shuō)明每個(gè)單獨(dú)的元素都是一個(gè)最長(zhǎng)遞增子序列，數(shù)組中所有元素都遞減或者相等，此時(shí)直接返回?cái)?shù)組長(zhǎng)度n即可。
count[ i ]表示到達(dá)第i個(gè)元素且長(zhǎng)度為L(zhǎng)[ i ]的子序列的數(shù)目，初始全為0，i=1到n，每次掃描第i個(gè)元素之前的所有元素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 對(duì)應(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;
    }
};