倒卖战利品

按照一个维度排序后按照另一个维度寻找最长增加子序列即可，这个是>=的比较简单一点，注意不能用O(n2)，要二分查找优化

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] ans = new int[n][2];
        for(int i=0;i<n;i++){
            ans[i][0] = scanner.nextInt();
            ans[i][1] = scanner.nextInt();
        }
        Arrays.sort(ans,(a,b)->a[0]!=b[0]?a[0]-b[0]:a[1]-b[1]);
        int[] arr = new int[n];
        for(int i=0;i<n;i++)arr[i] = ans[i][1];
        System.out.println(LIS(arr));
    }
    public static int LIS(int[] arr){
        int[] dp = new int[arr.length];
        int res = 0;
        for(int num:arr){
            int l = 0,r = res;
            while (l<r){
                int m = (l+r)/2;
                if(dp[m]<num)l = m+1;
                else r = m;
            }
            dp[l] = num;
            if(l==res)res++;
        }
        return res;
    }
}

import sys
class Z:
    def __init__(self,x,h):
        self.x = x
        self.h = h
    def __lt__(self,obj):
        if self.x != obj.x:
            return self.x < obj.x
        else:
            return self.h <obj.h

N = int(input())
z_list =[]
for i in range(N):
    x,h = map(int,sys.stdin.readline().strip().split())
    z_list.append(Z(x,h))

z_list.sort()
arr = [item.h for item in z_list]

def binary_search(arr1,start,end,target):
    if start < end:
        mid =(start+end)//2
        if arr1[mid]< target:#去找大于等于的位置
            return binary_search(arr1,mid+1,end,target)
        else:
            return binary_search(arr1,start,mid,target)
    else:
        return start


len_list=[arr[0]]
for index in range(1,len(arr)):
    item = arr[index]
    pos = binary_search(arr1 =len_list,start=0,end=len(len_list),target= item)
   
    if len(len_list)==pos:
        len_list.append(item)
    else:
        len_list[pos]=item
print(len(len_list))

import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n =sc.nextInt();
        int[][] arr=new int[n][2];
        for(int i=0;i<n;i++){
            arr[i][0]=sc.nextInt();
            arr[i][1]=sc.nextInt();
        }
        Arrays.sort(arr,(a,b)->a[0]==b[0] ? a[1]-b[1]:a[0]-b[0]);
        //用lambda改写构造器，按照第一个元素大小升序，相等则按照第二个元素倒序
        //a[1]-b[1]>0,则a[1],b[1]交换位置
        
        int[] nArr=new int[n];
        for(int i=0;i<n;i++) nArr[i]=arr[i][1];
        System.out.println(nout(nArr));
    }
        public static int out(int[] nArr){//寻找最长增子序列动态规划
            int result=0;
            int len=nArr.length;
            int[] dp=new int[len];
            //dp[i]代表以nArr[i]结尾的上升子序列长度!!!
            Arrays.fill(dp,1);
            for(int i=1;i<len;i++){
                for(int j=0;j<i;j++){
                    if(nArr[i]>nArr[j])
                        dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            for(int i=0;i<len;i++){
                result=Math.max(result,dp[i]);
            }
            return result;
        }    
    public static int nout(int[] nArr){//优化后
          int len = nArr.length;
        if (len <= 1) {
            return len;
        }

        // tail 数组的定义：长度为 i + 1 的上升子序列的末尾最小是几
        int[] tail = new int[len];
        // 遍历第 1 个数，直接放在有序数组 tail 的开头
        tail[0] = nArr[0];
        // end 表示有序数组 tail 的最后一个已经赋值元素的索引
        int end = 0;

        for (int i = 1; i < len; i++) {
            // 【逻辑 1】比 tail 数组实际有效的末尾的那个元素还大
            if (nArr[i] > tail[end]) {
                // 直接添加在那个元素的后面，所以 end 先加 1
                end++;
                tail[end] = nArr[i];
            } else {
                // 使用二分查找法，在有序数组 tail 中
                // 找到第 1 个大于等于 nums[i] 的元素，尝试让那个元素更小
                int left = 0;
                int right = end;
                while (left < right) {
                    // 选左中位数不是偶然，而是有原因的，原因请见 LeetCode 第 35 题题解
                    // int mid = left + (right - left) / 2;
                    int mid = left + ((right - left) >>> 1);
                    if (tail[mid] < nArr[i]) {
                        // 中位数肯定不是要找的数，把它写在分支的前面
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                // 走到这里是因为 【逻辑 1】 的反面，因此一定能找到第 1 个大于等于 nums[i] 的元素
                // 因此，无需再单独判断
                tail[left] = nArr[i];
            }
            // 调试方法
            // printArray(nums[i], tail);
        }
        // 此时 end 是有序数组 tail 最后一个元素的索引
        // 题目要求返回的是长度，因此 +1 后返回
        end++;
        return end;
    }

}


//out是动态规划，通过率只有80%
//nout优化后，通过了
借鉴了楼上大哥的

分析

• 思路 先对数组排序(sort函数会同时对两个维度排序，第一个维度相同时会比较第二个维度)，然后在另一个维度上搜索最长上升子序列。

 input: [[32],[11],[13],[12]]

sorted(input):[[11],[12],[13],[32]]

• 时间复杂度的限制：在找最长上升子序列时不能使用DP方法(O(N^2))，考虑通过二分查找来找到LIS。
• LIS的二分查找算法：参考: leetcode 300.最长上升子序列
  • 构造单调上升数组res，对原数组nums逐个遍历：
    • 如果nums[i]>res[-1]，说明满足上升条件，将其插入数组中；
    • 否则，通过二分查找res数组中刚好比它大的值并进行替换。当完成多次替换后该数组的最大值会减小，从而能向res中添加一些原数组中较小的值。
  • 计算数组的长度得到LIS的最大值。
• 注意二分搜索时的边界以及返回值选择

def binary_search(nums,left,right,val):
    mid = 0
    while left < right:
        mid = (left+right) // 2
        if val > nums[mid]:
            left = mid +1
        else:
            right = mid
    return left

def LIS(N,prices):
    res = []
    for i in range(N):
        if not res or prices[i] > res[-1]:
            res.append(prices[i])
        else:
            idx = binary_search(res, 0, len(res), prices[i])
            res[idx] = prices[i]
    return len(res)

def main():
    N = int(input())
    prices = []
    for i in range(N):
        prices.append(list(map(int,input().split())))
    prices.sort()
    h = [a[1] for a in prices]
    return LIS(N,h)

print(main())

这种思路比较容易理解：但是只有60%通过率，时间复杂度太高了

import sys

def helper(res):
    res.sort()
    nums = []
    for i in res:
        nums.append(i[1])
    #对nums进行一次最长上升子序列即可
    dp = [1]*len(nums)

    for i in range(len(nums)):
        for j in range(i):
            if nums[j]<nums[i]:
                dp[i] = max(dp[i],dp[j]+1)
    return max(dp)

    pass
if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    res = []
    for i in range(n):
        line = sys.stdin.readline().strip()
        values = list(map(int, line.split(' ')))
        res.append(values)
    out = helper(res)
    print(out)

def binaysearch(nums,left,right,val):
    while left < right:
        mid = (left + right) // 2
        if nums[mid] >= val:
            right = mid
        elif nums[mid] < val:
            left = mid + 1
    return left
            
def ans(nums,num):
    nums = sorted(nums,key = lambda x:(x[0],x[1]))
    temp = [0]*num
    for i in range(num):
        temp[i] = nums[i][1]
    res = []
    for i in range(num):
        if res == []&nbs***bsp;res[-1] < temp[i]:
            res.append(temp[i])
        else:
            idx = binaysearch(res, 0, len(res), temp[i])
            res[idx] = temp[i]
    return len(res)
   
if __name__ == "__main__":
    num = int(input()) #宝物的数量
    nums = []
    for i in range(num):
        nums.append(list(map(int,input().split())))
    print(ans(nums,num))

//参考大佬们的方法，注意这题的最长子序列需要>=而不是>
import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[][] nums = new int[n][2];
            for (int i = 0; i < n; i++) {
                nums[i][0] = sc.nextInt();
                nums[i][1] = sc.nextInt();
            }
            sc.close();

            Arrays.sort(nums, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

            int[] f = new int[n];
            f[0] = nums[0][1];
            int idx = 0;

            for (int i = 1; i < n; i++) {
                if (nums[i][1] >= f[idx]) {
                    f[++idx] = nums[i][1];
                } else {
                    int lo = 0, hi = idx;
                    while (lo < hi) {
                        int m = (hi - lo) / 2 + lo;
                        if (f[m] < nums[i][1]) {
                            lo = m + 1;
                        } else {
                            hi = m;
                        }
                    }
                    f[lo] = nums[i][1];
                }
            }
            System.out.println(idx + 1);
        }
    }

n = int(input())
WoW_goods = []
for i in range(n):
    goods = list(map(int, input().split()))
    WoW_goods.append(goods)
# print(WoW_goods)
WoW_goods.sort(key=lambda x: [x[0], x[1]])
# print(WoW_goods)
H = [WoW[1] for WoW in WoW_goods]
# print(H)
LIS = [H[0]]
import bisect
for i in range(1, n):
    idx = bisect.bisect_left(LIS, H[i])
    if idx==len(LIS):
        LIS.append(H[i])
    else:
        LIS[idx] = H[i]
print(len(LIS))

n = int(input())
places = [ list(map(int,input().split())) for _ in range(n)]
places.sort(key=lambda l:(l[0],l[1]),reverse=False) # print(places) dp = [1] for i in range(1,len(places)):
    max_dp = 0  for j in range(0,i): if places[i][1] > places[j][1] and dp[j]>max_dp:
            max_dp = dp[j]
    dp.append(max_dp+1)
max_dp = 0 for i in dp: if i>max_dp:
        max_dp = i print(max_dp)