JavaScript program to find the longest bimodal subsequence | DP-15

We will use dynamic programming to find the longest bitonic sequence in each array. A bitonal sequence is a sequence that first increases and then decreases. To find the longest bitonal sequence we will use a two-step approach. First, find the longest increasing subsequence in the given array, then find the longest decreasing subsequence in the reverse order of the given array. Finally, we add the lengths of the two subsequences and subtract 1 to exclude the common elements in the middle.

method

A bitonic sequence is a sequence that first increases and then decreases. The way to find the longest bitonal sequence in a given array is to use dynamic programming.

• Initialize two arrays "inc" and "dec", used to store the length of the longest increasing subsequence ending at each index.

• Loop through the array, updating the values ​​of "inc" and "dec" at each index using the value at the previous index.

• Find the maximum value of the sum of "inc" and "dec" minus one at each index, as this will give the length of the longest bit-increasing subsequence containing that index.

• Return the maximum value found in step 3 as the length of the longest bit-increasing subsequence.

• To reconstruct the longest bitonal sequence, use the values ​​in "inc" and "dec" to backtrack starting from the index that gave the maximum value in step 3.

• Return the reconstructed sequence as the longest bitonal sequence.

Example

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

Explanation

• The first step is to initialize two arrays, lis and lds, with the same length as the input array arr and filled with 1. lis represents "the longest increasing subsequence", lds represents the "longest decreasing subsequence".

• The next step is to calculate lis[i], which is the length of the longest increasing subsequence ending with arr[i]. This is accomplished through nested loops where j ranges from 0 to i-1. If arr[i] > arr[j], we update lis[i] to the maximum of its current value and lis[j] 1 .

• The next step is to calculate lds[i], which is the length of the longest descending subsequence starting from arr[i]. This is done via nested loops where j ranges from n-1 to i 1. If arr[i] > arr[j], we update lds[i] to its current value and the maximum value of lds[j] 1 .

• Finally, we loop through the n elements of the input array and find the maximum value of lis[i] lds[i] - 1, which means arr[i] is the length of the longest bit sequence at the end and starting point. This value is stored in the variable maxLength.

• This function returns maxLength, which is the length of the longest bit-increasing subsequence in the input array.

The above is the detailed content of JavaScript program to find the longest bimodal subsequence | DP-15. For more information, please follow other related articles on the PHP Chinese website!