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