主题:求最长递增子序列
birdfly324
[专家分:20] 发布于 2005-10-07 09:46:00
求最长递增子序列,可以不连续,如1 5 2 8 3 6 7选1 2 3 6 7,只用算出序列长度
回复列表 (共2个回复)
沙发
fuch [专家分:250] 发布于 2005-10-08 22:00:00
经典dp……
板凳
xuzhenyi [专家分:850] 发布于 2005-10-13 22:20:00
那个合唱队形就是这个玩艺
动态规划
思路是以每一个数字(项)作为升序的最后一项
label 1
然后往前推其实就是
While a[j]<a[k] and j<k do
inc(length);
有一个小的就在计数器上+1(长度) 然后节点移到那个小的上面 GOTO 1
直到全部弄好把长度记下并且保存上面的子串
接下来比较
比较出最大的 输出
我来回复