子集

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


public class Main {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        //T表示有T组数据
        int T = sc.nextInt();
        for (int i = 1; i <= T; i++)
        {
            //n表示有n个物品
            int n = sc.nextInt();
            //t[i][0]表示第i个物品的x属性，t[i][1]表示第i个物品的y属性，
            int[][] t = new int[n][2];
            int[] nums = new int[n];
            for (int j = 0; j < n; j++)
            {
                t[j][0] = sc.nextInt();
            }
            for (int j = 0; j < n; j++)
            {
                t[j][1] = sc.nextInt();
            }
            //x相同的情况下y更大的排序在前面（不然的话会重复统计相同的x）
            Arrays.sort(t, new Comparator<int[]>()
            {
                @Override
                public int compare(int[] o1, int[] o2)
                {
                    if(o1[0] > o2[0])
                        return 1;
                    else if(o1[0] < o2[0])
                        return -1;
                    else
                    {
                        if(o1[1] > o2[1])
                            return -1;
                        else if(o1[1] < o2[1])
                            return 1;
                        else
                            return -1;
                    }
                }
            });

            for (int j = 0; j < n; j++)
            {
                nums[j] = t[j][1];
            }
            int result = longestSubArray(nums);
            System.out.println(result);

        }
    }
    public static int longestSubArray(int[] nums)
    {
        //tails[k] 的值代表长度为k+1子序列 的尾部元素值
        int[] tails = new int[nums.length];
        // res 为 tails当前长度
        int res = 0;
        for (int num:nums)
        {
            int l = 0;
            //r为数组的长度，而不是length-1，这点要注意
            int r = res;
            while(l < r)
            {
                int m = l + (r - l)/2;
                if(tails[m] < num)
                    l = m + 1;
                else
                    r = m;
            }
            tails[l] = num;
            if(r == res)
                res++;
        }
        return  res;
    }
}




 

贪心+二分法

核心思路是将X排序，这样就可以在排序好的X对应的Y中，寻找最长的递增不一定连续的子序列了，这样的子序列代表最后的能挑出的最多的物品。时间复杂度为O(nlogn)

import java.io.*;
import java.util.*;
 
public class Main{
  //排序器，将X从小到大排序，最关键的一步是将相同的X按Y从大到小排序，因为如果按Y从小到大排序，
  //会导致后面的大的Y覆盖末尾前面的小的Y，这样就不符合贪心算法的尽量保证末尾元素最小的要求了。
    private static Comparator<int[]> comparator = new Comparator<int[]>(){
        @Override
        public int compare(int[] o1,int[] o2){
            if (o1[0] > o2[0]) return 1;
            else if (o1[0] < o2[0]) return -1;
            else {
                if (o1[1] > o2[1]) return -1;
                else if (o1[1] == o2[1]) return 0;
                else return 1;
            }
        }
    };

    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        int n = Integer.parseInt(str);
        for (int i = 0;i < n;i++){
            String str1 = bf.readLine();
            int m = Integer.parseInt(str1);
            String[] str2 = bf.readLine().split(" ");
            String[] str3 = bf.readLine().split(" ");
            int[][] items = new int[m][2];
            for (int j = 0;j < m;j++){
                items[j] = new int[]{Integer.parseInt(str2[j]),Integer.parseInt(str3[j])};
            }
            
            //对数组排序
            Arrays.sort(items,comparator);
            //res保存最长递增子序列的大小。
            int res = 1;
            //用来保存每个长度末尾的Y尽可能小的[x,y]数组。
            int[][] dp = new int[m + 1][2];
            dp[1] = items[0];
            //二分法进行查找此时的Y刚刚好大于哪一个下标的Y，又小于下一个下标的Y，这样更改下一个下标
            //的Y，为此时的Y，就可以保证dp数组保存的是末尾可能的最小的Y。这种方法相对于DP寻找最长
            //递增子序列，更快，时间复杂度为O(nlogn)
            for (int j = 1;j < m;j++){
                if (dp[res][1] < items[j][1]) dp[++res] = items[j];
                else if (dp[res][1] > items[j][1]){
                    int l = 1,r = res,pos = 0;
                    while (l <= r){
                        int mid = (l + r) >> 1;
                        if (dp[mid][1] < items[j][1]){
                            pos = mid;
                            l = mid + 1;
                        }else{
                            r = mid - 1;
                        }
                    }
                    if (dp[pos][0] != items[j][0]) dp[pos + 1] = items[j];
                }
            }
            System.out.println(res);
        }
    }
}

DP方法

dp方法时间复杂度为O(n^2),但是这题不能通过

import java.io.*;
import java.util.*;
 
public class Main{
  //排序器，将X从小到大排序，最关键的一步是将相同的X按Y从大到小排序，因为如果按Y从小到大排序，
  //会导致后面的大的Y覆盖末尾前面的小的Y，这样就不符合贪心算法的尽量保证末尾元素最小的要求了。
    private static Comparator<int[]> comparator = new Comparator<int[]>(){
        @Override
        public int compare(int[] o1,int[] o2){
            if (o1[0] > o2[0]) return 1;
            else if (o1[0] < o2[0]) return -1;
            else {
                if (o1[1] > o2[1]) return -1;
                else if (o1[1] == o2[1]) return 0;
                else return 1;
            }
        }
    };

    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        int n = Integer.parseInt(str);
        for (int i = 0;i < n;i++){
            String str1 = bf.readLine();
            int m = Integer.parseInt(str1);
            String[] str2 = bf.readLine().split(" ");
            String[] str3 = bf.readLine().split(" ");
            int[][] items = new int[m][2];
            for (int j = 0;j < m;j++){
                items[j] = new int[]{Integer.parseInt(str2[j]),Integer.parseInt(str3[j])};
            }
            
            //对数组排序
            Arrays.sort(items,comparator);
            //dp数组保存的是至今这个下标位置，最大的非连续递增序列的长度。
            int res = 0;
            int[] dp = new int[m];
            for (int j = 0;j < m;j++){
                dp[j] = 1;
                for (int l = 0;l < j;l++){
                    if (items[l][0] < items[j][0] && items[l][1] < items[j][1]) dp[j] = Math.max(dp[j],dp[l] + 1);
                }
                res = Math.max(dp[j],res);
            }
            System.out.println(res);
        }
    }
}

给个 Python 能过的

from bisect import bisect_left
T = int(input())
for _ in range(T):
    n = int(input())
    X = map(int, input().split())
    Y = map(int, input().split())
    a = sorted(zip(X, Y), key=lambda x: (x[0], -x[1]))
    total = 0
    q = [0] * 100005
    for i in range(n):
        t = bisect_left(a=q, x=a[i][1], lo=0, hi=total)
        if t == total:
            total += 1
        q[t] = a[i][1]
    print(total)

假如用了 dataclass 会 TLE

from __future__ import annotations

from bisect import bisect_left
from dataclasses import dataclass


@dataclass
class node:
    x: int
    y: int

    def __lt__(self, other: node):
        if self.x != other.x:
            return self.x < other.x
        return self.y > other.y


T = int(input())
for _ in range(T):
    n = int(input())
    X = map(int, input().split())
    Y = map(int, input().split())
    a = sorted(node(*x) for x in zip(X, Y))
    total = 0
    q = [0] * 100005
    for i in range(n):
        t = bisect_left(a=q, x=a[i].y, lo=0, hi=total)
        if t == total:
            total += 1
        q[t] = a[i].y
    print(total)

//最长上升子序列
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T,N;
    cin >> T;
    while((T--) > 0){
        cin >> N;
        vector<vector<int>> XY(N, vector<int>(2));
        for(int i = 0;i < N;i++){
            cin >> XY[i][0];
        }
        for(int i = 0;i < N;i++){
            cin >> XY[i][1];
        }
        //按照x升序排序
        sort(XY.begin(), XY.end(), [&](const auto &l, const auto &r){
            return (l[0] == r[0])? l[1] > r[1]:l[0] < r[0];
        });
        //对每个i进行二分查找
        //dp[i]表示前i项最后一项
        vector<int> dp(N+1);
        dp[1] = XY[0][1];
        int len = 1;
        for(int i = 1;i < N;i++){
            //对每个元素寻找最长递增子序列
          if(XY[i][1] > dp[len]){
              dp[++len] = XY[i][1];
          } else{
              int l = 1, r = len, k = 0;
              while(l <= r){
                  int mid = (l+r)>>1;
                  //找到小于XY[i][1]的最小dp
                  if(dp[mid] < XY[i][1]){
                      k = mid;
                      l = mid+1;
                  }else{
                      r = mid-1;
                  }
              }
              dp[k+1] = XY[i][1];
          }
        }
        printf("%d\n", len);
    }
}

C++奉上

#include<bits/stdc++.h>
using namespace std;
//一眼就能看出来是固定一个维度后的最长递增子序列问题，和力扣里的俄罗斯套娃问题、马戏团搭人梯问题类似
int helper(vector<vector<int>>& nums, int n){
    sort(nums.begin(), nums.end(), [&](auto& a, auto& b){
        if(a[0] == b[0]) return a[1] > b[1];
        return a[0] < b[0];
    });
    //这里用贪心+二分+dp来从O（n2）优化为O（nlogn）
    vector<int> f;
    f.push_back(nums[0][1]);
    for(int i = 1; i < n; i++){
        if(nums[i][1] > f.back()) f.push_back(nums[i][1]);
        else{
            auto it = lower_bound(f.begin(), f.end(), nums[i][1]);
            *it = nums[i][1];
        }
    }
    return f.size();
}
int main(){
    int count;
    cin >> count;
    while(count-- > 0){
        int n;
        cin >> n;
        vector<vector<int>> nums(n, vector<int>(2));
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < n; j++){
                cin >> nums[j][i];
            }
        }
        cout << helper(nums, n) << endl;
    }
}

import java.util.*;

public class Main {

    /**
     * 阿里1：小强现在有个物品,每个物品有两种属性和.他想要从中挑出尽可能多的物品满足以下条件:
     * 对于任意两个物品和,满足或者.问最多能挑出多少物品.
     * 3
     * 1 3 2
     * 0 2 3
     * 输出：2
     * 最长递增子序列
     */

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        for(int i=0;i<m;i++){
            int n = in.nextInt();
            int[][] arr = new int[n][2];
            for(int j=0;j<n;j++)
                arr[j][0] = in.nextInt();
            for(int j=0;j<n;j++)
                arr[j][1] = in.nextInt();
            //按x从小到大排序，如果x相等，按y从大到小排序
            Arrays.sort(arr, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0];
                }
            });
            System.out.println(LIS(arr,n));
        }
    }
    //求最长递增子序列
    public static int LIS(int[][] arr,int n){
        //dp[i]记录长度为i的递增序列中的最大值
        int[] dp = new int[n+1];
        int k=1;
        dp[k] = arr[0][1];
        for(int j=1;j<n;j++){
            if(arr[j][1]>dp[k])
                dp[++k] = arr[j][1];//大于dp[k] k才加，确保dp递增
            else {
                int left = 1;
                int right = k;
                int mid = (left+right)/2;
                while(left<=right){
                    mid = (left+right)/2;
                    if(arr[j][1]>dp[mid])
                        left = mid+1;
                    else
                        right = mid-1;
                }
                dp[right+1] = arr[j][1];//更新比他小的最大值的下一个，因为下一个一定大于等于他
            }
        }
        return k;
    }

}

import java.util.Scanner;
import java.util.Collections;
import java.util.Scanner;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m=in.nextInt();
        for(int i=0;i<m;++i) { // 注意 while 处理多个 case
            int n = in.nextInt();
            ArrayList<int[]> property = new ArrayList<>();
            for(int j=0;j<n;++j){
                property.add(new int[2]);
                property.get(j)[0]=in.nextInt();
            }
            for(int j=0;j<n;++j){
                property.get(j)[1]=in.nextInt();
            }
            Collections.sort(property, new Comparator<int[]>(){
                @Override
                public int compare(int[] a, int[] b){
                    return a[0]==b[0]?b[1]-a[1]:a[0]-b[0];
                }
            });
            int res=0;
            ArrayList<Integer> stack=new ArrayList<>();
            stack.add(property.get(0)[1]);
            for(int j=1;j<n;++j){
                int k=stack.size()-1;
                if(stack.get(k)<property.get(j)[1]){
                    stack.add(property.get(j)[1]);
                    continue;
                }
                while(k>=0&&stack.get(k)>=property.get(j)[1]){
                    k--;
                }
                stack.set(k+1,property.get(j)[1]);
            }
            System.out.println(stack.size());
        }
    }
}