【題解】LeetCode 673. Number of Longest Increasing Subsequence

class Solution {
public:
    int findNumberOfLIS(vector<int>& n) {
        vector <int> v[n.size()+1];
        int cnt[2005] = {};
        int mx = 1;
        v[1].push_back(0);
        cnt[0] = 1;
        for (int i = 1; i < n.size(); i++){
            for (int j = mx; j >= 1; j--){
                if (v[j].empty()) continue;
                bool flag = false;
                for (int k:v[j]){
                    if (n[k] < n[i]){
                        if (!flag){
                            flag = true;
                            v[j+1].push_back(i);
                            mx = max(mx, j+1);
                        }
                        cnt[i] += cnt[k];
                    }
                }
                if (flag) break;
            }
            if (!cnt[i]){
                cnt[i] = 1;
                v[1].push_back(i);
            }
        }
        int ans = 0;
        for (int i:v[mx]){
            ans += cnt[i];
        }
        return ans;
    }
};