最长递增子序列的个数

这道题在 最长递增子序列 的基础上，记录额外的信息：g(i)g(i) 表示以 aia_i 结尾的 LIS 的个数。

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

    return ans;
  }
};