第17章 笔试题

import java.util.Arrays;
import java.util.Scanner;

public class XYSort {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            int n = sc.nextInt();
            int[][] goods = new int[n][2];
            for (int j = 0; j < n; j++) {
                goods[j][0] = sc.nextInt();
            }
            for (int j = 0; j < n; j++) {
                goods[j][1] = sc.nextInt();
            }

            Arrays.sort(goods, (int[] goods1, int[] goods2) -> {
                if (goods1[0] == goods2[0]) {
                    return goods2[1] - goods1[1];//降序
                }
                return goods1[0] - goods2[0];//升序
            });
            int[] temp = new int[n];
            for (int j = 0; j < n; j++) {
                temp[j] = goods[j][1];
            }
            System.out.println(findMaxSequence(temp));
        }
    }

    private static int findMaxSequence(int[] nums) {
        int length = nums.length;
        //dp[i]为长度为i+1的所有的子序列中末尾元素最小值
        int dp[] = new int[length];
        int end = 0;//标记此时dp的末尾
        dp[end] = nums[end];
        for (int i = 1; i < length; i++) {
            if (nums[i] > dp[end]) {
                dp[++end] = nums[i];
            } else {
                int left = 0, right = end;
                while (left < right) {
                    int mid = left + right >> 1;
                    if (dp[mid] < nums[i]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                dp[left] = nums[i];
            }
        }
        return end + 1;
    }
}