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)); 

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