[code="java"]public class MissileIntercept {
public static void main(String[] args) {
intercept(new int[] { 389, 207, 155, 300, 299, 170, 158, 65 });
}
private static void intercept(int[] array) {
int n = array.length;
int[] d = new int[n];
int dmax, xh;
for (int i = n - 2; i >= 0; i--) { // 从后往前计算d[i]值
for (int j = i + 1; j < n; j++) {
if ((array[j] <= array[i]) && (d[i] < d[j] + 1)) {
d[i] = d[j] + 1;
}
}
}
dmax = 0;
xh = 1;
for (int i = 0; i < n; i++) { // 求出dmax
if (d[i] > dmax) {
dmax = d[i];
xh = i;
}
}
System.out.println(dmax); // 输出结果
System.out.print(array[xh] + " ");
int temp = xh;
for (int i = xh + 1; i < n; i++) {
if (d[i] == d[temp] - 1) {
temp = i;
System.out.print(array[i] + " ");
}
}
System.out.println();
}
}[/code]