最长递增子串问题(Longest Increase Subsequence, 简称LIS):
给定一组无序数字a1,a2…an，求其最长的递增子串长度。递增子串即ak1,ak2…akm，其中k1<k2<..<km，且ak1<ak2<…<akm了，此问题即是求km的最大值。
Robin博客
思路:
此问题可以用动态规划的方法求解。 设f(i)为以ai结尾的最长递增子串，根据LIS的性质容易得出，对于任意f(i)，其数值等于所有j<i且aj<ai的f(j)集合的最大值加上1。据此可以写出求f(i)的动态规划范式:
f(i) = max{ f(1), f(2), f(3) ... f(j) } + 1 ( j<i & aj<ai)
LIS即为max{f(1),f(2),f(3)...f(n)} vickiexu.com
伪代码:
Vickie博客
get_lis(L) {
f[0] = 1;
for(i <- 1 to n)
for(j <- 0 to i)
if(L[j] < L[i] && f[j] >= f[i])
f[i] = f[j] + 1
end if
end for
end for
lis = 1
for(i <- 0 to n)
if(f[i] > lis)
lis = f[i]
end if
end for
return lis
}
robin.sh
