หา Longest Bitonic Subsequence

ลำดับ Bitonic คือลำดับที่เพิ่มขึ้นก่อน แล้วตามด้วยการลดลง เราต้องการหา subsequence ที่เป็น bitonic และมีความยาวมากที่สุด

แนวคิดแก้ปัญหา

แบ่งเป็น 2 ส่วน:

1. LIS (Longest Increasing Subsequence): incSubSeq[i] = ความยาว LIS ที่ลงท้ายด้วย array[i]
2. LDS (Longest Decreasing Subsequence): decSubSeq[i] = ความยาว LDS ที่เริ่มจาก array[i]

ความยาว Bitonic ที่ผ่าน array[i] = incSubSeq[i] + decSubSeq[i] - 1 (ลบ 1 เพราะ array[i] นับซ้ำ)

ตัวอย่าง Input และ Output

Input: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Output: ความยาว Longest Bitonic Subsequence = 7

อัลกอริทึม

ขั้นตอน:

1. คำนวณ LIS (ซ้ายไปขวา):
   เริ่ม incSubSeq[i] = 1 ทุกค่า
   • for i = 1 ถึง n-1, j = 0 ถึง i-1:
     ถ้า array[i] > array[j] และ incSubSeq[i] < incSubSeq[j] + 1 → incSubSeq[i] = incSubSeq[j] + 1
2. คำนวณ LDS (ขวาไปซ้าย):
   เริ่ม decSubSeq[i] = 1 ทุกค่า
   • for i = n-2 ถึง 0, j = n-1 ถึง i+1:
     ถ้า array[i] > array[j] และ decSubSeq[i] < decSubSeq[j] + 1 → decSubSeq[i] = decSubSeq[j] + 1
3. หาค่าสูงสุด: max(incSubSeq[i] + decSubSeq[i] - 1) สำหรับทุก i

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

#include <iostream>
#include <algorithm>
using namespace std;

int longBitonicSub(int arr[], int size) {
    int *incSubSeq = new int[size];
    for (int i = 0; i < size; i++)
        incSubSeq[i] = 1;

    // LIS จากซ้ายไปขวา
    for (int i = 1; i < size; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && incSubSeq[i] < incSubSeq[j] + 1)
                incSubSeq[i] = incSubSeq[j] + 1;

    int *decSubSeq = new int[size];
    for (int i = 0; i < size; i++)
        decSubSeq[i] = 1;

    // LDS จากขวาไปซ้าย
    for (int i = size-2; i >= 0; i--)
        for (int j = size-1; j > i; j--)
            if (arr[i] > arr[j] && decSubSeq[i] < decSubSeq[j] + 1)
                decSubSeq[i] = decSubSeq[j] + 1;

    int max = incSubSeq[0] + decSubSeq[0] - 1;
    for (int i = 1; i < size; i++)
        if (incSubSeq[i] + decSubSeq[i] - 1 > max)
            max = incSubSeq[i] + decSubSeq[i] - 1;

    delete[] incSubSeq;
    delete[] decSubSeq;
    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 << "Length of longest bitonic subsequence is " 
         << longBitonicSub(arr, n);
    return 0;
}

Output

Length of longest bitonic subsequence is 7

ความซับซ้อน

• Time: O(n²)
• Space: O(n)