lc.673.最长上升子序列个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1),cnt(n,1);
        int maxLen = 1;
        for(int i=1;i<n;++i) {
            for(int j=0;j<i;++j) {
                if(nums[j]< nums[i]) {
                    if(dp[j] + 1> dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    }else if(dp[j] +1 == dp[i]) {
                        cnt[i] = cnt[i] + cnt[j];
                    }
                }
            }
            maxLen = max(maxLen,dp[i]);
        }
        int res = 0;
        for(int i=0;i<n;++i)
        {
            if(dp[i] == maxLen) {
                res = res + cnt[i];
            }
        }
        return res;
    }
};