Sample Input
5
1 4 2 5 -12
4
-12 1 2 4
Sample Output
2
1 4 题目：给你两个数字序列，求出这两个序列的最长公共上升子序列。
输出最长的长度，并打表输出。可能存在多种正确答案，故此题是special judge！ 分析：dp[i][j] : A[1...i]和B[1...j]的公共上升子序列中以B[j]为结尾的最长的长度。
如果A[i] != B[j], 则dp[i][j]=d[i-1][j]; 也就是说当前这个A[i]是没效用的。
如果A[i] = B[j], 则dp[i][j]=max( dp[i][k]+1 ),其中 k<j 且 A[i]>B[k]
时间复杂度O(n^2) 注意：
n1 n2位两个序列的长度，
A[] B[]为两个序列数组，
ans 全局变量 最长公共子序列的长度值
lcis 最长公共上升子序列 打表存储 代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm> using namespace std; int n1, n2;
int A[510], B[510];
int dp[510][510];
int pre[510][510];
int lcis[510];
int ans; void get_LCIS()
{
memset(dp, 0, sizeof(dp));
memset(pre, 0, sizeof(pre));
int i, j;
for(i=1; i<=n1; i++){
int k=0;
for(j=1; j<=n2; j++){
if(A[i] != B[j]) dp[i][j]=dp[i-1][j];
if(A[i]>B[j] && dp[i][j]>dp[i][k]) k=j;
if(A[i]==B[j]){
dp[i][j]=dp[i][k]+1;
pre[i][j]=k;
}
}
}
ans=-1;
int x=n1, y=0;
for(i=1; i<=n2; i++){
if(dp[n1][i]>ans){
ans=dp[n1][i]; y=i;
}
}
int cnt=1;
while(dp[x][y]){
if(A[x] != B[y]) x--;
else{
lcis[ans-cnt]=B[y];
cnt++;
y=pre[x][y];
}
}
} int main()
{
scanf("%d", &n1);
for(int i=1; i<=n1; i++) scanf("%d", &A[i]);
scanf("%d", &n2);
for(int i=1; i<=n2; i++) scanf("%d", &B[i]); get_LCIS();
printf("%d\n", ans );
for(int i=0; i<ans; i++)
printf("%d%c", lcis[i], i==ans-1?'\n':' '); return 0;
}