数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 中最长的递增序列的总数
问题
我们需要编写一个 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
更新时间： 2021 年 4 月 24 日
755 次浏览
广告