题解 | 拦截导弹

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        int index = 0;
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            nums[index] = in.nextInt();
            index++;
        }
        // 第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int res = dp[0];
        // 最大连续下降序列
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] <= nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                res = Math.max(res, dp[i]);
            }
        }
        // 最少要多少个系统，不同的系统拦截的数量是不一样的，比如某个系统最大拦截6，另外一个系统最大拦截可能就是3了，所以需要统计
        // Dilworth定理：最少的下降序列个数等于整个序列最长上升子序列的长度
        // 本质上是在计算最长递增子序列的长度，因为每出现一个比之前所有的高的导弹，就需要新增一个系统
        int count = 0;
        int[] dp2 = new int[n];
        Arrays.fill(dp2,1);
        for(int i = 1; i < n;i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp2[i] = Math.max(dp2[i], dp2[j] + 1);
                }
            }
        }
        for(int i = 0; i < n; i++){
            count = Math.max(count, dp2[i]);
        }
        
        System.out.println(res);
        System.out.println(count);
    }
}