最长递增子序列的个数

定义 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度，cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数。设 nums 的最长上升子序列的长度为 maxLen ，那么答案为所有满足 dp[i]=maxLen 的 i 所对应的 cnt[i] 之和。

class Solution {
 public:
  int findNumberOfLIS(vector<int> &nums) {
    int n = nums.size(), maxLen = 0, ans = 0;
    vector<int> dp(n), cnt(n);
    for (int i = 0; i < n; ++i) {
      dp[i] = 1;
      cnt[i] = 1;
      for (int j = 0; j < i; ++j) {
        if (nums[i] > nums[j]) {
          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[j];
          }
        }
      }
      if (dp[i] > maxLen) {
        maxLen = dp[i];
        ans = cnt[i];
      } else if (dp[i] == maxLen) {
        ans += cnt[i];
      }
    }
    return ans;
  }
};