我们将使用动态规划在每个数组中找到最长的双调子序列。双调子序列是首先递增，然后递减的序列。为了找到最长的双调子序列，我们将采用两步方法。首先，在给定的数组中找到最长的递增子序列，然后在给定数组的逆序中找到最长的递减子序列。最后，我们将两个子序列的长度相加，并减去1以排除中间的公共元素。
方法
一个双调序列是指首先递增然后递减的序列。在给定数组中找到最长双调子序列的方法是使用动态规划。
初始化两个数组"inc"和"dec"，用于存储以每个索引结尾的最长递增子序列的长度。
-
循环遍历数组，在每个索引处使用前一个索引处的值更新"inc"和"dec"的值。
立即学习“Java免费学习笔记（深入）”；
找到每个索引处“inc”和“dec”之和减一的最大值，因为这将给出包含该索引的最长比特递增子序列的长度。
将在步骤3中找到的最大值作为最长比特递增子序列的长度返回。
要重构最长的双调子序列，请使用“inc”和“dec”中的值，从在步骤3中给出最大值的索引开始回溯。
将重构的序列作为最长的双调子序列返回。
Example
的中文翻译为：示例
Here is a complete working example of a JavaScript program to find the longest bitonic subsequence using dynamic programming −
function LBSLength(arr) {
let n = arr.length;
let lis = new Array(n).fill(1);
let lds = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
lis[i] = Math.max(lis[i], lis[j] + 1);
}
}
}
for (let i = n - 2; i >= 0; i--) {
for (let j = n - 1; j > i; j--) {
if (arr[i] > arr[j]) {
lds[i] = Math.max(lds[i], lds[j] + 1);
}
}
}
let maxLength = 0;
for (let i = 0; i < n; i++) {
maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);
}
return maxLength;
}
const arr = [1, 7, 8, 11, 5, 2, 3];
console.log(LBSLength(arr));
Explanation
的中文翻译为：解释
第一步是初始化两个数组，lis 和lds，长度与输入数组arr 相同，并填充为1。 lis 代表“最长递增子序列”，lds 代表“最长递减子序列”。
下一步是计算 lis[i]，即以 arr[i] 结尾的最长递增子序列的长度。这是通过嵌套循环来实现的，其中 j 的范围从 0 到 i-1。如果 arr[i] > arr[j]，我们将 lis[i] 更新为其当前值和 lis[j] + 1 的最大值。
下一步是计算lds[i]，即以arr[i]为起点的最长递减子序列的长度。这是通过嵌套循环来完成的，其中j的范围从n-1到i+1。如果arr[i] > arr[j]，我们将lds[i]更新为其当前值和lds[j] + 1的最大值。
最后，我们循环遍历输入数组的n个元素，并找到lis[i] + lds[i] - 1的最大值，它表示以arr[i]为结尾和起点的最长比特序列的长度。这个值被存储在变量maxLength中。
该函数返回maxLength，它是输入数组中最长比特递增子序列的长度。
