导弹拦截系统-最长降序序列

引用

Problem
中国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在使用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

Input
最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000的正整数）

Output
两个整数M和N。表示：这套系统最多能拦截 M 枚导弹，如果要拦截所有导弹最少要配备 N 套这种导弹系统。

Sample Input
300 250 275 252 200 138 245

Sample Output
5 2

思路：
1.算出每个数字后面都几个小于自己的数字(factor)
2.由最大factor的数字开始替归，寻找往下比自己小，但factor又最大的那个值
3.由这些值串起来，就成了最长的降序序列。

def defend(missiles,fightStack)
	return nil if !missiles || missiles.size==0
	missilesSize = missiles.size
	factors = Array.new(missilesSize)
	largest_f_index = missilesSize-1
	largest_f = 0
	missiles.size.downto(1){|i|
		index = i-1		
		m = missiles.at(index).to_i		
		m_factor = 0
		(i...missilesSize).each{|j|
			m_back = missiles.at(j).to_i			
			m_factor += 1 if m_back<m
		}
		factors[index] = m_factor	
		(largest_f_index=index;largest_f=m_factor)if  m_factor >largest_f
	}		
	return getFightStack(largest_f_index,missiles,factors,fightStack)	
end
def getFightStack(beginIndex,data,factors,fightStack)
		return fightStack if beginIndex>=data.length		
		m = data.at(beginIndex)
		m_factor = factors.at(beginIndex)
		fightStack << m		
		nextIndex = beginIndex+1
		biggestIndex=data.size
		biggestF = 0
		(nextIndex...data.size).each{|j|
			nextM = data.at(j)
			nextF = factors.at(j)			
			(biggestF=nextF;biggestIndex=j) if nextM<m && nextF>=biggestF			
		}	
		getFightStack(biggestIndex,data,factors,fightStack)	
end

#
$data = Array.[](300,250,275,252,200,138,240)
m_data = $data
count = 0
while true
	fightStack = defend(m_data,Array.new)
	break if !fightStack
	bestSolution = fightStack if count==0
	count += 1
	m_data = m_data- fightStack
end

p bestSolution
p bestSolution.size
p count