[673] 最长递增子序列的个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

输入：[1,3,5,4,7]

输出：2

解释：有两个最长递增子序列，分别是 [1, 3, 4, 7] 和 [1, 3, 5, 7]。

示例 2:

输入：[2,2,2,2,2]

输出：5

解释：最长递增子序列的长度是 1，并且存在 5 个子序列的长度为 1，因此输出 5。

提示：

1 <= nums.length <= 2000

-10^6 <= nums[i] <= 10^6

这道题是 [300] 最长递增子序列 的升级版，建议理解了该题后再来做这道题。

这道题不仅需要我们找出最长递增子序列，并且同时还需要输出形成组成最长子序列的可能个数。

这里我们需要建立一个 count[i] 数组，来存储 i 位置下，组成该最长子序列长度 dp[i] 时的可能个数。

当发现 dp[i] 与被判断值相等时，需要将当前与被判断位置两种情况的 count 个数相加来更新 count[i] 的值。

当 dp[i] 更新时，也需要重置当前位置的 count[i] 与被判断位置相等。

function findNumberOfLIS(nums: number[]): number {
  let res = 1;
  let max = 1;
  const dp = Array(nums.length).fill(1);
  const count = Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        if (dp[i] < dp[j] + 1) {
          dp[i] = dp[j] + 1;
          count[i] = count[j];
        } else if (dp[i] === dp[j] + 1) {
          count[i] += count[j];
        }
      }
    }

    if (max < dp[i]) {
      max = dp[i];
      res = count[i];
    } else if (max === dp[i]) {
      res += count[i];
    }
  }

  return res;
}