資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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，它是輸入陣列中最長位元尼克子序列的長度。
174 次檢視
