> For the complete documentation index, see [llms.txt](https://shangan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shangan.gitbook.io/algorithm/he-xin-suan-fa-200-ti/basic-dynamic-programming-and-coordinate-dynamic-programming/russian-doll-envelopes.md).

# Russian Doll Envelopes

{% tabs %}
{% tab title="Java" %}

```java
public class Solution {
    /**
     * @param envelopes a number of envelopes with widths and heights
     * @return the maximum number of envelopes
     */
    public int maxEnvelopes(int[][] envelopes) {
        // Write your code here
        if(envelopes == null || envelopes.length == 0 
            || envelopes[0] == null || envelopes[0].length != 2)
            return 0;
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] arr1, int[] arr2){
                if(arr1[0] == arr2[0])
                    return arr2[1] - arr1[1];
                else
                    return arr1[0] - arr2[0];
            } 
        });
        int dp[] = new int[envelopes.length];
        int len = 0;
        for(int[] envelope : envelopes){
            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
                if(index < 0)
                    index = -index - 1;
            dp[index] = envelope[1];
            if (index == len)
                len++;
        }
        return len;
    }
}
```

{% endtab %}
{% endtabs %}

![](https://2784211123-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M-ELB26IpzCEJWSDi0m%2F-M-wnIcBcHKi4Mi0XoNz%2F-M-aDeCjXr_sq2EEcjRc%2FWechatIMG1754.png?alt=media\&token=56a9049e-4041-4910-a5c8-81443f2adbbf)