给定两个整数序列,写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列:
存在 1 <= i1 < i2 < . . . < iN <= M ,使得对所有 1 <= j <=N,均有Sj = Aij,且对于所有的1 <= j < N,均有Sj < Sj+1。
每个序列用两行表示,第一行是长度M(1 <= M <= 500),第二行是该序列的M个整数Ai (-231 <= Ai < 231 )
在第一行,输出两个序列的最长上升公共子序列的长度L。在第二行,输出该子序列。如果有不止一个符合条件的子序列,则输出任何一个即可。
5
1 4 2 5 -12
4
-12 1 2 4
2
1 4
#include<iostream>
#include<algorithm>
#include<cstring>
#include <string>
using namespace std;
int main()
{
int a[2][501],m1,m2,f[2][501];
string g[2][501];
cin >> m1;
for (int i = 1; i <= m1; i++)
cin >> a[0][i];
cin >> m2;
for (int i = 1; i <= m2; i++)
cin >> a[1][i];
for (int i = 1; i <= m1; i++)
{
int _max_ = 0;
string __max__;
for (int j = 1; j <= m2; j++)
{
f[1][j] = f[0][j];
g[1][j] = g[0][j];
if (a[0][i] > a[1][j])
{
if (_max_<f[0][j])
{
_max_ = f[0][j];
__max__ = g[0][j];
}
}
if (a[0][i] == a[1][j])
{
f[1][j] = _max_ + 1;
g[1][j] = __max__ + " "+to_string(a[0][i]);
}
}
for (int j = 1; j <= m2; j++)
{
f[0][j] = f[1][j];
g[0][j] = g[1][j];
}
}
int len = 0;
string max_;
for (int i = 1; i <= m2; i++)
{
if (len < f[1][i])
{
len = f[1][i];
max_ = g[1][i];
}
}
cout << len << endl;
cout << max_.substr(1, max_.size() - 1) << endl;
return 0;
}
目前的问题是,有某一个测试点报错Runtime Error。题目所在的网站无法查看测试点,因此查不出报错的原因。
请大神赐教。