Number of Longest Increasing Subsequence LeetCode solution in C++

1
class Solution {
2
 public:
3
  int findNumberOfLIS(vector<int> &nums) {
4
    int n = nums.size(), maxI = 0, inc = 0;
5
    vector<int> dp(n, 1), count(n, 1);
6
    for (int i = 0; i < n; i++) {
7
      for (int j = 0; j < i; j++) {
8
        if (nums[i] > nums[j] && 1 + dp[j] > dp[i]) {
9
          dp[i] = 1 + dp[j];
10
          count[i] = count[j];
11
        } else if (nums[i] > nums[j] && 1 + dp[j] == dp[i])
12
          count[i] += count[j];
13
      }
14
      maxI = max(maxI, dp[i]);
15
    }
16
    for (int i = 0; i < n; i++)
17
      if (maxI == dp[i]) inc += count[i];
18
    return inc;
19
  }
20
};