โปรแกรม C++ หาลำดับย่อยเพิ่มที่ยาวที่สุด (Longest Increasing Subsequence)

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

Input: ชุดจำนวนเต็ม {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Output: ความยาว LIS คือ 6 ลำดับย่อยคือ 0, 2, 6, 9, 13, 15

อัลกอริทึม

longestSubSeq(subarray, n)

Input: อาร์เรย์ย่อยและขนาดของอาร์เรย์

Output: ความยาวของลำดับย่อยเพิ่มที่ยาวที่สุด

Begin
    กำหนดอาร์เรย์ length ขนาด n
    ตั้งค่าเริ่มต้นทุกค่าใน length เป็น 0
    for i := 1 ถึง n-1 ทำ
        for j := 0 ถึง i-1 ทำ
            ถ้า subarray[j] < subarray[i] และ length[j] > length[i] แล้ว
                length[i] := length[j]
            จบ if
        จบ for j
        เพิ่ม length[i] ขึ้น 1
    จบ for i
    lis := 0
    for i := 0 ถึง n-1 ทำ
        lis := ค่าสูงสุดระหว่าง lis และ length[i]
    จบ for i
    return lis
End

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

#include <iostream>
using namespace std;

int longestSubSeq(int subArr[], int n) {
    int length[n] = { 0 }; // ตั้งค่าทุกค่าเป็น 0
    length[0] = 1; // ลำดับย่อยที่จบด้วย subArr[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]++; // เพิ่ม arr[i] เข้าไป
    }
    
    int lis = 0;
    for (int i = 0; i < n; i++) // หา LIS
        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;
}

ผลลัพธ์

Length of Longest Increasing Subsequence is: 6