Number of Longest Increasing Subsequence

Description

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Solution(javascript)

// /** DFS
//  * @param {number[]} nums
//  * @return {number}
//  */
// const findNumberOfLIS = function (nums) {
//   const visited = new Array(nums.length).fill(false)
//   const distance = new Array(nums.length).fill(1).map(() => [1, 1])
//   let max = 1
//   const dfs = (index) => {
//     if (visited[index]) {
//       return distance[index]
//     }
//     visited[index] = true
//     let maxDistance = 1
//     let totalCount = 0
//     for (let i = index + 1; i < nums.length; i++) {
//       if (nums[i] > nums[index]) {
//         const [currentDistance] = dfs(i)
//         maxDistance = Math.max(currentDistance + 1, maxDistance)
//       }
//     }
//     max = Math.max(maxDistance, max)
//     for (let i = index + 1; i < nums.length; i++) {
//       if (nums[i] > nums[index]) {
//         const [currentDistance, currentCount] = dfs(i)
//         if (currentDistance + 1 === maxDistance) {
//           totalCount += currentCount
//         }
//       }
//     }
//     distance[index] = [maxDistance, totalCount === 0 ? 1 : totalCount]
//     return distance[index]
//   }
//   for (let i = 0; i < nums.length; i++) {
//     dfs(i)
//   }
//   return distance.reduce((acc, [currentDistance, count]) => {
//     if (currentDistance === max) {
//       acc += count
//     }
//     return acc
//   }, 0)
// }

// /** DP1
//  * @param {number[]} nums
//  * @return {number}
//  */
// const findNumberOfLIS = function (nums) {
//   const distance = new Array(nums.length).fill(1).map(() => 1)
//   const count = new Array(nums.length).fill(1).map(() => 1)
//   let max = 1
//   for (let i = 0; i < nums.length; i++) {
//     for (let j = 0; j < i; j++) {
//       if (nums[j] < nums[i]) {
//         if (distance[i] <= distance[j]) {
//           distance[i] = distance[j] + 1
//           count[i] = count[j]
//           max = Math.max(distance[i], max)
//         } else if (distance[i] === distance[j] + 1) {
//           count[i] += count[j]
//         }
//       }
//     }
//   }
//   return distance.reduce((acc, d, index) => {
//     if (d === max) {
//       acc += count[index]
//     }
//     return acc
//   }, 0)
// }

/** DP2
 * @param {number[]} nums
 * @return {number}
 */
const findNumberOfLIS = function (nums) {
  const distance = new Array(nums.length).fill(1).map(() => 1)
  const count = new Array(nums.length).fill(1).map(() => 1)
  let max = 1
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) {
        if (distance[j] <= distance[i]) {
          distance[j] = distance[i] + 1
          count[j] = count[i]
          max = Math.max(distance[j], max)
        } else if (distance[j] === distance[i] + 1) {
          count[j] += count[i]
        }
      }
    }
  }
  return distance.reduce((acc, d, index) => {
    if (d === max) {
      acc += count[index]
    }
    return acc
  }, 0)
}