Leetcode Russian Doll Envelopes problem solution

class Solution:
    def maxEnvelopes(self, A: List[List[int]]) -> int:
        A.sort(key=lambda x: (x[0], -x[1]))
        tails = [inf] * len(A)
        size = 0
        for w in map(lambda x: x[1], A):
            i = bisect_left(tails, w)
            tails[i] = w
            size = max(i + 1, size)
        return size

class Solution {
    private Map<Long, Integer> map = new HashMap<>();
    public int maxEnvelopes(int[][] envelopes) {
        return dfs(envelopes, new int[]{-1, -1});
    }
    private int dfs(int[][] envelopes, int[] curr) {
        long key = (curr[0] + curr[1]) * (curr[0] + curr[1] + 1) / 2 + curr[1];
        if(map.containsKey(key)) return map.get(key);
        int res = Integer.MIN_VALUE;
        for(int[] e : envelopes) {
            if(e[0] > curr[0] && e[1] > curr[1]) {
                res = Math.max(res, dfs(envelopes, e));
            }
        }
        if(res == Integer.MIN_VALUE) {
            res = 0;
        }else {
            res++;
        }
        map.put(key, res);
        return res;
    }
}

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& a) {
        int n=(int)a.size();
        assert(n>0);
        vector<int>dp;
        sort(a.begin(),a.end(),[&](vector<int>&x,vector<int>&y){
            return x[0]<y[0] || (x[0]==y[0] && x[1]>y[1]); 
        });
        dp.emplace_back(a[0][1]);
        for(int i=1;i<n;++i){
            int cur_height=a[i][1];
            auto it=lower_bound(dp.begin(),dp.end(),cur_height);
            if(it==dp.end())
                dp.emplace_back(cur_height);
            else if(*it>cur_height)
                dp[it-dp.begin()]=cur_height;
        }
        return dp.size();
    }
};