A,B两数组之间有交集,A数组大于B数组,求AB子数组的最长长度


A:[2,2,2,2,3,3,3,5,6]
B:[2,3,2,5,4]
定义的子数组是一个或几个连续的子集,比如,[2,3]是AB的子数组,[3,2]是B的子数组,但不是A的数组,[5,4]是B的数组
写出AB子数组的最长的长度

php 数组

剑圣尤多娜 8 years, 11 months ago

最长公共子序列问题。

X,Y分别表示两个序列X,设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有:
f[1][1] = same(1,1);
f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}
其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”,否则为“0”。

撸腿毛 answered 8 years, 11 months ago

Your Answer