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

สมมติว่าเรามีรายการตัวเลข เราต้องการหาความยาวของลำดับย่อยบิทอนิก (Bitonic Subsequence) ที่ยาวที่สุด ลำดับบิทอนิกคือลำดับที่เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) แล้วตามด้วยการลดลงอย่างเคร่งครัด (strictly decreasing) ลำดับที่เพิ่มขึ้นอย่างเดียวหรือลดลงอย่างเดียวก็ถือเป็นบิทอนิกเช่นกัน

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

ขั้นตอนการแก้ปัญหา

• สร้างอาร์เรย์ increasingSubSeq ขนาดเท่าอินพุต เติมค่า 1
• คำนวณ LIS (Longest Increasing Subsequence) สำหรับแต่ละตำแหน่ง:
  • วน i จาก 1 ถึง size-1, j จาก 0 ถึง i-1
  • ถ้า arr[i] > arr[j] และ increasingSubSeq[i] < increasingSubSeq[j] + 1: อัปเดตค่า
• สร้างอาร์เรย์ decreasingSubSeq ขนาดเท่าอินพุต เติมค่า 1
• คำนวณ LDS (Longest Decreasing Subsequence) จากท้ายมาหน้า:
  • วน i จาก size-2 ลงมาที่ 0, j จาก size-1 ลงมาที่ i+1
  • ถ้า arr[i] > arr[j] และ decreasingSubSeq[i] < decreasingSubSeq[j] + 1: อัปเดตค่า
• หาค่าสูงสุดของ increasingSubSeq[i] + decreasingSubSeq[i] - 1 สำหรับทุก i
• คืนค่าค่าสูงสุดนั้น

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int longBitonicSub(int arr[], int size) {
    int *increasingSubSeq = new int[size];
    for (int i = 0; i < size; i++)
        increasingSubSeq[i] = 1;
    for (int i = 1; i < size; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSubSeq[i] < increasingSubSeq[j] + 1)
                increasingSubSeq[i] = increasingSubSeq[j] + 1;

    int *decreasingSubSeq = new int[size];
    for (int i = 0; i < size; i++)
        decreasingSubSeq[i] = 1;
    for (int i = size - 2; i >= 0; i--)
        for (int j = size - 1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
                decreasingSubSeq[i] = decreasingSubSeq[j] + 1;

    int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
    for (int i = 1; i < size; i++)
        if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
            max = increasingSubSeq[i] + decreasingSubSeq[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 << longBitonicSub(arr, n);
}

อินพุต

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

เอาต์พุต

7