这个问题源于线性代数中的问题。
问题描述:设一个整数序列为A,A={a0,a1,a2,......, an}。其中任意一个递增子序列为Sk,Sk={ai,....,aj,......}, 其中ai,aj为Ak序列中任意两个元素且i<j。ai<aj。A的所有递增子序列集合为S(Sk),找出最长的Sk,即得到了最长递增子序列的长度。
举个例子,7,3,6,5,7 它的最长递增子序列为3,5,7。长度为3。
LIS问题动态规划解决方法
算法:取A中的元素ai,计算以ai结尾的必须包含ai的最长子递增序列L(i)。遍历序列A,得到 L(i)的集合L。从L中找出最长的元素L(i),即为最长的递增子序列。
解释:设最长......
阅读全文