Red Huang

LIS の長さを計算する

2. int s [5];       // sequence を保存するための配列

3. int array [5];   // x 番目の値は sequence: s [0]~s [x] の LIS の長さ

4. int LIS()

5. {

6.     // 初期化、各数字は長さ 1 の部分列そのものである

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); // 1 つの 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. }