Red Huang

計算 LIS 的長度

2. int s [5];       // 用來存 序列

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

4. int LIS()

5. {

6.     // 初始化，每一個數字本身就是長度為一的 子序列

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

8.     // LIS

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

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

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

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

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

14.     int ans = 0;

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

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

17.     return ans;

18. }

找出一個 LIS

2. int s[5];

3. int array[5];

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

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

6. int LIS()

7. {

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

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

10.     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.                 }

19.     int ans = 0, pos = 0;

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

21.         if (ans > array[i])

22.         {

23.             ans = array[i];

24.             pos = i;

25.         }

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

27.     return ans;

28. }

29. // 遞迴版

30. void print_LIS(int x)

31. {

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

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

34. }

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

36. void print_LIS(int x)

37. {

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

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

40. }