Program JavaScript untuk mencari urutan bimodal terpanjang |

Kami akan menggunakan pengaturcaraan dinamik untuk mencari jujukan bitonal terpanjang dalam setiap tatasusunan. Jujukan bitonal ialah jujukan yang mula-mula meningkat dan kemudian menurun. Untuk mencari jujukan bitonal terpanjang kita akan menggunakan pendekatan dua langkah. Mula-mula, cari jujukan peningkatan terpanjang dalam tatasusunan yang diberikan, kemudian cari jujukan susut terpanjang dalam susunan terbalik tatasusunan yang diberikan. Akhir sekali, kami menambah panjang dua jujukan dan tolak 1 untuk mengecualikan unsur sepunya di tengah.

Kaedah

Jujukan bitonik ialah jujukan yang mula-mula meningkat dan kemudian menurun. Cara untuk mencari jujukan bitonal terpanjang dalam tatasusunan tertentu adalah dengan menggunakan pengaturcaraan dinamik.

• Mulakan dua tatasusunan "inc" dan "dec" untuk menyimpan panjang jujukan yang meningkat paling lama berakhir pada setiap indeks.

• Gelung melalui tatasusunan, mengemas kini nilai "inc" dan "dec" pada setiap indeks menggunakan nilai pada indeks sebelumnya.

• Cari nilai maksimum jumlah "inc" dan "dec" tolak satu pada setiap indeks, kerana ini akan memberikan panjang jujukan peningkatan bit terpanjang yang mengandungi indeks tersebut.

• Kembalikan nilai maksimum yang terdapat dalam langkah 3 sebagai panjang urutan peningkatan bit terpanjang.

• Untuk membina semula jujukan bitonal terpanjang, gunakan nilai dalam "inc" dan "dec" untuk mengundur bermula dari indeks yang memberikan nilai maksimum dalam langkah 3.

• Kembalikan urutan yang dibina semula sebagai jujukan bitonal terpanjang.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Berikut ialah contoh lengkap program JavaScript untuk mencari jujukan bitonik terpanjang menggunakan pengaturcaraan dinamik −

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

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

• Langkah pertama ialah untuk memulakan dua tatasusunan, lis dan lds, dengan panjang yang sama dengan tatasusunan input arr dan diisi dengan satu. lis bermaksud "jujukan susulan yang paling lama meningkat", lds bermaksud "urutan menurun paling lama".

• Langkah seterusnya ialah mengira lis[i], iaitu panjang jujukan peningkatan terpanjang yang berakhir dengan arr[i]. Ini dicapai melalui gelung bersarang di mana j berjulat dari 0 hingga i-1. Jika arr[i] > arr[j], kami mengemas kini lis[i] kepada nilai semasanya dan maksimum lis[j] + 1.

• Langkah seterusnya ialah mengira lds[i], iaitu panjang urutan menurun terpanjang bermula dari arr[i]. Ini dilakukan melalui gelung bersarang di mana j berjulat dari n-1 hingga i+1. Jika arr[i] > arr[j], kami mengemas kini lds[i] kepada maksimum nilai semasanya dan lds[j] + 1.

• Akhir sekali, kami mengulangi elemen n tatasusunan input dan mencari nilai maksimum lis[i] + lds[i] - 1, yang mewakili nilai maksimum berakhir dan bermula dengan arr[i] Panjang jujukan bit panjang. Nilai ini disimpan dalam pembolehubah maxLength.

• Fungsi ini mengembalikan maxLength, iaitu panjang jujukan peningkatan bit terpanjang dalam tatasusunan input.

Atas ialah kandungan terperinci Program JavaScript untuk mencari urutan bimodal terpanjang |. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!