1.子集

1. 题目描述

小强现在有阿里笔试算法题2021 - 图1 个物品,每个物品有两种属性阿里笔试算法题2021 - 图2 和阿里笔试算法题2021 - 图3 .他想要从中挑出尽可能多的物品满足以下条件:对于任意两个物品阿里笔试算法题2021 - 图4 和阿里笔试算法题2021 - 图5 ,满足阿里笔试算法题2021 - 图6 或者阿里笔试算法题2021 - 图7 .问最多能挑出多少物品.
进阶：时间复杂度阿里笔试算法题2021 - 图8 ，空间复杂度阿里笔试算法题2021 - 图9

2. 输入描述

第一行输入一个正整数T.表示有T组数据.
对于每组数据,第一行输入一个正整数n.表示物品个数.
接下来两行,每行有n个整数.
第一行表示n个节点的x属性.
第二行表示n个节点的y属性.

3. 输出描述

输出T行,每一行对应每组数据的输出.

4. 输入例子

2
3
1 3 2
0 2 3
4
1 5 4 2 
10 32 19 21

5. 输出例子

2
3

6. 思路

最长上升子序列的变种，需要保证xy的同升同降，即先将所有物品按x升序排列，随后在无序的y中取一个最长上升子序列即可，同样两种解法，dp和二分，但是本题在牛客上只能二分，dp会报超时。

7. 代码解析

最长递增子序列解析：
解法一：动态规划，O(n^2)
初始值：dp[0] = 1。
双循环，设value[i]为以元素arr[i]结尾的子序列的最大长度，求出当前元素arr[i]前边的值arr[0, i-1]的最大值，则：
dp[i] = arr[i]>max(dp[0,i-1])? dp[i-1]+1 : dp[i-1]
解法二：二分查找优化，O(nlog2n)

package com.kuaishou;

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

/**
 * 阿里笔试题目：子集
 * 最长上升子序列的变种
 */
public class test {

    public static class Good implements Comparable{
        public int x;
        public int y;
        public Good(int xx, int yy) {
            x = xx;
            y = yy;
        }
        @Override
        public int compareTo(Object o) {
            Good good = (Good) o;
            if (this.x > good.x) {
                return 1;
            } else if (this.x < good.x) {
                return -1;
            } else {
                //x相同，y大的放前边
                if (this.y > good.y) {
                    return -1;
                } else if (this.y < good.y){
                    return 1;
                }
                return 0;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            int goodsNum = sc.nextInt();

            int[] linearr1 = new int[goodsNum];
            int[] linearr2 = new int[goodsNum];
            for (int j = 0; j < linearr1.length; j++) {
                linearr1[j] = sc.nextInt();
            }
            for (int j = 0; j < linearr2.length; j++) {
                linearr2[j] = sc.nextInt();
            }
            sc.nextLine();
            Good[] goods = new Good[goodsNum];
            for (int j = 0; j < goods.length; j++) {
                goods[j] = new Good(linearr1[j], linearr2[j]);
            }
            // 按x升序排序
            Arrays.sort(goods);

            // 剩下的就是按y的排列来获取最大上升子序列长度问题
            // 代码与上边两个简单的几乎一致，动态规划dp O(n^2)
            dp(goods);

            // 二分查找优化 O(nlog2n)
            binarySearch(goods);
        }
    }

    private static void binarySearch(Good[] arr) {
        int[] value = new int[arr.length +1];
        int maxLength = 1;
        value[1] = arr[0].y;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].y > value[maxLength]) {
                value[++maxLength] = arr[i].y;
            } else {
                int t = find(value, maxLength, arr[i].y);
                value[t] = arr[i].y;
            }
        }
        System.out.println(maxLength);
    }

    /**
     * 动态规划解决，复杂度n2
     * @param arr
     */
    private static void dp(Good[] arr) {
        int maxLength = 0;

        // 数组元素value[i]表示以arr[i]为子序列最后一位时，递增子序列的最大长度
        int[] value = new int[arr.length];

        // 每次循环获取 以arr[i]为子序列最后一位时，递增子序列最大长度
        for (int i = 0; i < arr.length; i++) {
            // 默认都是长度1
            value[i] = 1;

            // 循环第0位到第 i - 1 位value[]，找出最大递增序列长度maxvalue
            // 则value[i] = maxvalue + 1;
            for (int j = 0; j < i; j++) {
                if (arr[i].y > arr[j].y) {
                    value[i] = Math.max(value[j] + 1, value[i]);
                }
            }
            // 找出最大的那个
            maxLength = Math.max(maxLength, value[i]);
        }
        System.out.println(maxLength);
    }

    private static int find(int[] value, int maxindex, int i) {
        int l = 1, r = maxindex;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (i > value[mid]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}