JavaScript程序查找最长比特尼克子序列 | DP-15

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

方法

比特尼克序列是指先递增后递减的序列。在给定数组中找到最长比特尼克子序列的方法是使用动态规划。

  • 初始化两个数组“inc”和“dec”，以存储以每个索引结尾的最长递增子序列的长度。

  • 遍历数组，使用先前索引处的值更新每个索引处的“inc”和“dec”的值。

  • 找到每个索引处“inc”和“dec”之和减一的最大值，因为这将给出包含该索引的最长比特尼克子序列的长度。

  • 将步骤 3 中找到的最大值作为最长比特尼克子序列的长度返回。

  • 要重建最长的比特尼克子序列，请使用“inc”和“dec”中的值从步骤 3 中给出最大值的索引回溯。

  • 将重建的序列作为最长的比特尼克子序列返回。

示例

这是一个使用动态规划查找最长比特尼克子序列的 JavaScript 程序的完整工作示例 -

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

更新于：2023年3月15日

174 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告