โปรแกรมหาความยาวของบิโทนิกที่ยาวที่สุดใน C++

สมมติว่าเรามีรายการตัวเลข เราต้องหาลำดับย่อยของบิโทนิกที่ยาวที่สุด Aswe ผูกลำดับว่ากันว่าเป็น bitonic ถ้ามันเพิ่มขึ้นอย่างเคร่งครัดแล้วลดลงอย่างเคร่งครัด ลำดับที่เพิ่มขึ้นอย่างเข้มงวดคือบิตโทนิก หรือลำดับที่ลดลงอย่างเคร่งครัดก็เป็นบิตโทนิกเช่นกัน

ดังนั้น หากอินพุตเป็น nums =[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], ขนาดลำดับ 16 แล้ว ผลลัพธ์จะเป็น 7

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

เพิ่มSubSeq :=อาร์เรย์ใหม่ของขนาดอาร์เรย์ที่กำหนด และเติม 1
สำหรับการเริ่มต้น i :=1 เมื่อฉัน <ขนาด อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- สำหรับการเริ่มต้น j :=0 เมื่อ j

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#includeใช้เนมสเปซ std;int longBitonicSub( int arr[], int size ) { int *increasingSubSeq =new int[ขนาด]; สำหรับ (int i =0; i arr[j] &&การเพิ่มขึ้นSubSeq[i] <เพิ่มSubSeq[j] + 1) เพิ่มSubSeq[i] =เพิ่มSubSeq[j] + 1; int *decreasingSubSeq =ใหม่ int [ขนาด]; สำหรับ (int i =0; i =0; i--) สำหรับ (int j =size-1; j> i; j--) if (arr[i]> arr[j] &&decreasingSubSeq[i ] max) max =กำลังเพิ่มSubSeq[i] + ลดลง SubSeq[i] - 1; return max;}int main() { int arr[] ={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; int n =16; cout <
อินพุต
<ก่อน>[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

ผลลัพธ์

7