JavaScript程序以找到最长的双峰子序列

JavaScript程序以找到最长的双峰子序列 | DP-15

我们将使用动态规划在每个数组中找到最长的双调子序列。双调子序列是首先递增，然后递减的序列。为了找到最长的双调子序列，我们将采用两步方法。首先，在给定的数组中找到最长的递增子序列，然后在给定数组的逆序中找到最长的递减子序列。最后，我们将两个子序列的长度相加，并减去1以排除中间的公共元素。

方法

一个双调序列是指首先递增然后递减的序列。在给定数组中找到最长双调子序列的方法是使用动态规划。

初始化两个数组"inc"和"dec"，用于存储以每个索引结尾的最长递增子序列的长度。
循环遍历数组，在每个索引处使用前一个索引处的值更新"inc"和"dec"的值。
找到每个索引处“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));

Salin selepas log masuk

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，它是输入数组中最长比特递增子序列的长度。