JavaScript 中最长递增序列的总数

• Z时代
• 2024-01-10
• 分类：综合

问题

我们需要编写一个 JavaScript 函数，它接受一个数字数组 arr 作为第一个也是唯一的参数。

我们的函数需要找到最长递增子序列（连续或非连续）的数量。

例如，如果函数的输入是

输入

const arr = [2, 4, 6, 5, 8];

输出

const output = 2;

输出说明

两个最长的递增子序列是 [2, 4, 5, 8] 和 [2, 4, 6, 8]。

示例

以下是代码 -

const arr = [2, 4, 6, 5, 8];
const countSequence = (arr) => {
   const distance = new Array(arr.length).fill(1).map(() => 1)
   const count = new Array(arr.length).fill(1).map(() => 1)
   let max = 1
   for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; j++) {
         if (arr[j] > arr[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)
}
console.log(countSequence(arr));

2

以上是 JavaScript 中最长递增序列的总数 的全部内容， 来源链接： utcz.com/z/350479.html