#673 - Number of Longest Increasing Subsequence

Medium • View on LeetCode • View on GitHub

Problem Description

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function(nums) {
  const lengths = new Array(nums.length).fill(1);
  const counts = new 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 (lengths[j] + 1 > lengths[i]) {
          lengths[i] = lengths[j] + 1;
          counts[i] = counts[j];
        } else if (lengths[j] + 1 === lengths[i]) {
          counts[i] += counts[j];
        }
      }
    }
  }

  const max = Math.max(...lengths);
  return lengths.reduce((sum, l, i) => {
    return sum + (l === max ? counts[i] : 0);
  }, 0);
};