Longest Increasing Subsequence (LIS) ใน Java: Dynamic Programming

Longest Increasing Subsequence (LIS)

หา ความยาว ของ subsequence (ไม่ต้องติดกัน) ที่เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) และยาวที่สุด

ตัวอย่างโค้ด (DP O(n²))

public class Demo { 
    static int lisLength(int[] arr, int n) { 
        // dp[i] = ความยาว LIS ที่ลงท้ายด้วย arr[i]
        int[] dp = new int[n]; 
        
        // Base case: แต่ละตัวเองเป็น LIS ยาว 1
        for (int i = 0; i < n; i++) 
            dp[i] = 1; 
        
        // Fill DP table
        for (int i = 1; i < n; i++) { 
            for (int j = 0; j < i; j++) { 
                if (arr[i] > arr[j] && dp[i] < dp[j] + 1) { 
                    dp[i] = dp[j] + 1; 
                } 
            } 
        } 
        
        // หาค่าสูงสุดใน dp
        int max = 0; 
        for (int len : dp) 
            if (len > max) max = len; 
        
        return max; 
    } 
    
    public static void main(String[] args) { 
        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60}; 
        System.out.println("ความยาว LIS: " + lisLength(arr, arr.length)); 
    } 
}

ผลลัพธ์

ความยาว LIS: 5

คำอธิบาย (Trace)

Array: [10, 22, 9, 33, 21, 50, 41, 60]

i=0: dp[0]=1  (10)
i=1: 22>10 → dp[1]=dp[0]+1=2  (10,22)
i=2: 9 ไม่ > ใคร → dp[2]=1    (9)
i=3: 33>10,22,9 → max(dp[0],dp[1],dp[2])+1 = 3  (10,22,33)
i=4: 21>10,9 → max(1,1)+1=2    (10,21) หรือ (9,21)
i=5: 50>10,22,9,33,21 → max(1,2,1,3,2)+1=4  (10,22,33,50)
i=6: 41>10,22,9,33,21 → max(1,2,1,3,2)+1=4  (10,22,33,41)
i=7: 60>all → max(...)+1=5    (10,22,33,50,60) หรือ (10,22,33,41,60)

dp = [1, 2, 1, 3, 2, 4, 4, 5] -> max = 5

ความซับซ้อน

เวอร์ชัน O(n log n) - แนะนำสำหรับ n ใหญ่

import java.util.Arrays; 

public static int lisLengthOptimized(int[] arr) { 
    int[] tails = new int[arr.length]; 
    int size = 0; 
    
    for (int x : arr) { 
        // Binary search หาตำแหน่งแรกที่ >= x
        int i = Arrays.binarySearch(tails, 0, size, x); 
        if (i < 0) i = -(i + 1); // insertion point
        
        tails[i] = x; 
        if (i == size) size++; 
    } 
    return size; 
}

การสร้าง LIS จริง (ไม่ใช่แค่ความยาว)

// ต้องเก็บ parent pointer ใน DP O(n²)
int[] parent = new int[n]; 
// ... ในลูป DP ...
if (arr[i] > arr[j] && dp[i] < dp[j] + 1) { 
    dp[i] = dp[j] + 1; 
    parent[i] = j; 
}
// แล้ว backtrack จาก index ที่มี dp มากที่สุด