求最长上升公共子串
f【i】【j】表示a(1,i),b(1,j)取以b【j】结尾的最大公共上升子串的大小
当a【i】 != b【j】 时,f【i】【j】 = f【i - 1】【j】
否则:f【i】【j】 = max { f【i - 1】【(1……j - 1)】 && (a[i] > b[1……j - 1])};
#include <stdio.h>
#include <string.h> #include <stdlib.h> #define MAXN 205 int a[MAXN]; int f[MAXN][MAXN]; int main() { int T, N; for(scanf("%d", &T); T--; ) { scanf("%d", &N); for(int i = 1; i <= N; ++i) scanf("%d", &a[i]); memset(f, 0, sizeof(f)); int ans = 1; for(int i = 1; i <= N; ++i) { int max = 0; for(int j = N; i < j; --j) { f[i][j] = f[i-1][j];//假设不相等 if((a[i] == a[j]) && (f[i][j] < max + 1))//当相等 f[i][j] = max + 1; else if((a[i] > a[j]) &&(f[i-1][j] > max)) max = f[i-1][j];//在b串中,取一个以小于a【i】的结尾的最大长度 if(f[i][j] * 2 > ans) ans = f[i][j] * 2; for(int k = i + 1; k < j; ++k)//判断是否中间有一个比很大的数 { if(a[k] > a[j]) { if(2 * f[i][j] + 1 > ans) ans = 2 * f[i][j] + 1; } } } } printf("%d\n", ans); } return 0; }