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，它是輸入陣列中最長位元遞增子序列的長度。

以上是JavaScript程式以找出最長的雙峰子序列 | DP-15的詳細內容。更多資訊請關注PHP中文網其他相關文章！