หา Longest Increasing Subsequence (LIS)

Longest Increasing Subsequence (LIS) คือ subsequence ที่สมาชิกแต่ละตัวมีค่ามากกว่าตัวก่อนหน้า เราต้องการหาความยาวของ LIS จากชุดของจำนวนเต็ม

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

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

อัลกอริทึม Dynamic Programming (O(n²))

ฟังก์ชัน longestSubSeq(subarray, n)

แนวคิดหลัก:

กำหนด length[i] = ความยาว LIS ที่ลงท้ายด้วย subarray[i]

ขั้นตอน:

1. สร้างอาร์เรย์ length[n] เริ่มต้นทุกค่าเป็น 0
2. length[0] = 1 (subsequence ที่มีแค่ตัวแรก)
3. สำหรับ i = 1 ถึง n-1:
   • สำหรับ j = 0 ถึง i-1:
     • ถ้า subarray[j] < subarray[i] และ length[j] > length[i]
     • → length[i] = length[j]
   • length[i]++ (เพิ่มตัว subarray[i] เข้าไป)
4. หาค่า max(length[i]) สำหรับ i = 0 ถึง n-1

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

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

int longestSubSeq(int subArr[], int n) {
    int length[n] = {0};
    length[0] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (subArr[j] < subArr[i] && length[j] > length[i])
                length[i] = length[j];
        }
        length[i]++;
    }

    int lis = 0;
    for (int i = 0; i < n; i++)
        lis = max(lis, length[i]);

    return lis;
}

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 Increasing Subsequence is: " 
         << longestSubSeq(arr, n);
    return 0;
}

Output

Length of Longest Increasing Subsequence is: 6

ความซับซ้อน

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

เพิ่มเติม: วิธี O(n log n)

สามารถปรับปรุงเป็น O(n log n) ได้โดยใช้ Binary Search บนอาร์เรย์ tail[] ที่เก็บค่าสิ้นสุดที่เล็กที่สุดของ subsequence แต่ละความยาว