计算 LIS 的长度
-
int s [5]; // 用来存 sequence
-
int array [5]; // 第 x 格的值为 sequence: s [0]~s [x] 的 LIS 长度
-
int LIS()
-
{
-
// 初始化，每一个数字本身就是长度为一的subsequence -
for (int i=0; i<5; i++) array\[i\] = 1; -
// LIS -
for (int i=0; i<5; i++) -
for (int j=i+1; j<5; j++) // 找出能接在s\[i\]后面的数字 -
if (s\[j\] > s\[i\]) // 若是可以接，长度就增加 -
array\[j\] = max(array\[j\], array\[i\] + 1); -
// array中最大的值即为LIS的长度 -
int ans = 0; -
for (int i=0; i<5; i++) -
ans = max(ans, array\[i\]); -
return ans; -
}
找出一个 LIS
-
int s[5];
-
int array[5];
-
int prev [5]; //prev [x] 纪录 s [x] 是接在哪个位置的数字后面
-
// 如果它前面没有数字就纪录-1 -
int LIS()
-
{
-
for (int i=0; i<5; i++) array\[i\] = 1; -
// -1 代表这个数字没有接在其他数字之后 -
for (int i=0; i<5; i++) prev\[i\] = -1; -
for (int i=0; i<5; i++) -
for (int j=i+1; j<5; j++) -
if (s\[j\] > s\[i\]) -
if (array\[i\] + 1 > array\[j\]) -
{ -
array\[j\] = array\[i\] + 1; -
prev\[j\] = i; // s\[j\] 接在 s\[i\] 后面 -
} -
int ans = 0, pos = 0; -
for (int i=0; i<5; i++) -
if (ans > array\[i\]) -
{ -
ans = array\[i\]; -
pos = i; -
} -
print\_LIS(pos); // 印出一个LIS -
return ans; -
}
-
// 递归版
-
void print_LIS(int x)
-
{
-
if (prev\[x\] != -1) print\_LIS(prev\[x\]); -
cout << seq\[x\] << " "; -
}
-
// 迴圈版，但是顺序是颠倒的。
-
void print_LIS(int x)
-
{
-
for (; prev\[x\] != -1; x = prev\[x\]) -
cout << seq\[x\] << " "; -
}