673.最长递增子序列的个数

链接：673.最长递增子序列的个数
难度：Medium
标签：树状数组、线段树、数组、动态规划
简介：给定一个未排序的整数数组，找到最长递增子序列的个数。

题解 1 - javascript

• 编辑时间：2021-09-20
• 执行用时：108ms
• 内存消耗：40.5MB
• 编程语言：javascript
• 解法介绍：动态规划。

function findNumberOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(0).map(_ => ({ val: 1, cnt: 1 }));
  let maxVal = 1;
  let maxCnt = 0;
  for (let i = 0; i < n; i++) {
    const num = nums[i];
    for (let j = 0; j < i; j++) {
      if (nums[j] < num) {
        const len = dp[j].val + 1;
        if (dp[i].val < len) {
          dp[i].val = len;
          dp[i].cnt = dp[j].cnt;
        } else if (dp[i].val === len) dp[i].cnt += dp[j].cnt;
      }
    }
    if (maxVal < dp[i].val) {
      maxVal = Math.max(maxVal, dp[i].val);
      maxCnt = dp[i].cnt;
    } else if (maxVal === dp[i].val) maxCnt += dp[i].cnt;
  }
  return maxCnt;
}