Longest Increasing Subsequence: Dynamic Programming

計算 LIS 的長度

1. int s[5];       // 用來存 sequence


2. int array[5];   // 第 x 格的值為 sequence: s[0]~s[x] 的 LIS 長度


3. int LIS()


4. {


5.     // 初始化，每一個數字本身就是長度為一的 subsequence


6.     for (int i=0; i<5; i++) array[i] = 1;


7.     // LIS


8.     for (int i=0; i<5; i++)


9.         for (int j=i+1; j<5; j++)   // 找出能接在 s[i] 後面的數字


10.             if (s[j] > s[i])        // 若是可以接，長度就增加


11.                 array[j] = max(array[j], array[i] + 1);


12.     // array 中最大的值即為 LIS 的長度


13.     int ans = 0;


14.     for (int i=0; i<5; i++)


15.         ans = max(ans, array[i]);


16.     return ans;


17. }

找出一個 LIS

1. int s[5];


2. int array[5];


3. int prev[5];    // prev[x] 紀錄 s[x] 是接在哪個位置的數字後面


4.                 // 如果它前面沒有數字就紀錄 -1


5. int LIS()


6. {


7.     for (int i=0; i<5; i++) array[i] = 1;


8.     // -1 代表這個數字沒有接在其他數字之後


9.     for (int i=0; i<5; i++) prev[i] = -1;




11.     for (int i=0; i<5; i++)


12.         for (int j=i+1; j<5; j++)


13.             if (s[j] > s[i])


14.                 if (array[i] + 1 > array[j])


15.                 {


16.                     array[j] = array[i] + 1;


17.                     prev[j] = i;   // s[j] 接在 s[i] 後面


18.                 }




20.     int ans = 0, pos = 0;


21.     for (int i=0; i<5; i++)


22.         if (ans > array[i])


23.         {


24.             ans = array[i];


25.             pos = i;


26.         }


27.     print_LIS(pos); // 印出一個LIS


28.     return ans;


29. }




31. // 遞迴版


32. void print_LIS(int x)


33. {


34.     if (prev[x] != -1) print_LIS(prev[x]);


35.     cout << seq[x] << " ";


36. }




38. // 迴圈版，但是順序是顛倒的。


39. void print_LIS(int x)


40. {


41.     for (; prev[x] != -1; x = prev[x])


42.         cout << seq[x] << " ";


43. }