package com.kingdz.algorithm.time201706;
/**
* <pre>
* 拦截导弹
* 敌人发射了一批导弹，每个导弹有一定的高度
* 发射拦截导弹进行拦截，每个拦截导弹的高度不会高于前一次发生的高度
* 现在给定敌人导弹的高度列表，求一个系统可以最多拦截多少个导弹
* 如果需要全部拦截则需要多少个系统
* </pre>
*
* @author kingdz
*
*/
public class Algo06 {
public static void main(String[] args) {
int[] height = { 0, 120, 358, 350, 340, 287, 294, 265, 312, 198, 220 };
int[] flag = new int[height.length];
height[0] = Integer.MAX_VALUE;
for (int i = 1; i < height.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (height[j] >= height[i] && (flag[j] + 1 > flag[i])) {
flag[i] = flag[j] + 1;
}
}
}
int max = 0;
for (int i = 1; i < height.length; i++) {
if (flag[i] > max) {
max = flag[i];
}
}
System.out.println(max);
for (int i = 0; i < height.length; i++) {
flag[i] = 0;
}
height[0] = 0;
for (int i = 1; i < height.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (height[j] < height[i] && (flag[j] + 1 > flag[i])) {
flag[i] = flag[j] + 1;
}
}
}
int min = 0;
for (int i = 1; i < height.length; i++) {
if (flag[i] > min) {
min = flag[i];
}
}
System.out.println(min);
}
}
