JavaScript 查找最长Bitonic子序列

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

方法

Bitonic序列是一种先增加再减少的序列。在给定数组中找到最长Bitonic子序列的方法是使用动态规划。

初始化两个数组“inc”和“dec”，以存储以每个索引结束的最长递增子序列的长度。
循环遍历数组，使用先前索引处的值更新“inc”和“dec”的值。
找到每个索引处“inc”和“dec”之和减一的最大值，因为这将给出包含该索引的最长Bitonic子序列的长度。
返回步骤3中找到的最大值作为最长Bitonic子序列的长度。
为了重构最长的Bitonic子序列，使用“inc”和“dec”中的值从给出步骤3中最大值的索引开始回溯。
返回重构的序列作为最长的Bitonic子序列。

示例

这是一个完整可工作的JavaScript程序的示例，用于使用动态规划查找最长的Bitonic子序列 –

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

解释

第一步是初始化两个数组 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 ，即输入数组中最长山脉子序列的长度。