LIS - 💯🚀 single pattern to solve all LIS problems
300. Longest Increasing Subsequence\n213. House Robber II\n198. House Robber\n740. Delete and Earn\n\n\n\n# Code\njava []\nimport java.util.Arrays;\n\npublic cl
[300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/solutions/5574584/longest-increasing-subsequence-one-stop-template/)\n[213. House Robber II](https://leetcode.com/problems/house-robber-ii/solutions/5791343/house-robber-i-ii-beats-100/)\n[198. House Robber](https://leetcode.com/problems/house-robber/solutions/5791346/house-robber-pattern-and-variation-all-approaches/)\n[740. Delete and Earn](https://leetcode.com/problems/delete-and-earn/solutions/5791351/house-robber-variation/)\n\n\n\n# Code\n```java []\nimport java.util.Arrays;\n\npublic class Solution {\n    public int maxEnvelopes(int[][] envelopes) {\n        int n = envelopes.length;\n        if (n == 0) return 0;\n\n        // Sort envelopes by width. If two envelopes have the same width, sort by height in ascending order.\n        Arrays.sort(envelopes, (a, b) -> {\n            if (a[0] == b[0]) return a[1] - b[1]; // Sort by height if width is the same\n            return a[0] - b[0]; // Sort by width otherwise\n        });\n\n        // DP array to store the maximum number of envelopes ending at each index\n        int[] dp = new int[n];\n        Arrays.fill(dp, 1); // Every envelope is a standalone valid sequence, so initialize to 1\n\n        int maxEnvelopes = 1; // To store the maximum number of envelopes\n\n        // Loop through each envelope\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < i; j++) {\n                // Check if envelope[j] can fit into envelope[i]\n                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {\n                    dp[i] = Math.max(dp[i], dp[j] + 1); // Update dp[i] if we found a larger sequence\n                }\n            }\n            maxEnvelopes = Math.max(maxEnvelopes, dp[i]); // Update the maximum envelopes found so far\n        }\n\n        return maxEnvelopes; // Return the maximum number of envelopes\n    }\n}\n```\n```java []\npublic class Solution {\n    public int maxEnvelopes(int[][] envelopes) {\n        int n = envelopes.length;\n        if (n == 0) return 0;\n\n        // Step 1: Sort the envelopes by width in ascending order and by height in descending order\n        Arrays.sort(envelopes, (a, b) -> {\n            if (a[0] == b[0]) {\n                return b[1] - a[1]; // If widths are equal, sort by height in descending order\n            } else {\n                return a[0] - b[0]; // Otherwise, sort by width in ascending order\n            }\n        });\n\n        // Step 2: Extract the heights and apply LIS on them\n        int[] heights = new int[n];\n        for (int i = 0; i < n; i++) {\n            heights[i] = envelopes[i][1];\n        }\n\n        // Find the length of LIS on heights using binary search approach\n        return lengthOfLIS(heights);\n    }\n\n    // Helper function to find the length of LIS using binary search (efficient approach)\n    private int lengthOfLIS(int[] nums) {\n        List<Integer> lis = new ArrayList<>();\n        for (int num : nums) {\n            if (lis.isEmpty() || lis.get(lis.size() - 1) < num) {\n                lis.add(num);\n            } else {\n                // Find the position to replace in the LIS list\n                int pos = binarySearch(lis, num);\n                lis.set(pos, num);\n            }\n        }\n        return lis.size();\n    }\n\n    // Binary search to find the correct position to replace in the list\n    private int binarySearch(List<Integer> lis, int target) {\n        int low = 0, high = lis.size() - 1;\n        while (low <= high) {\n            int mid = low + (high - low) / 2;\n            if (lis.get(mid) == target) {\n                return mid;\n            } else if (lis.get(mid) < target) {\n                low = mid + 1;\n            } else {\n                high = mid - 1;\n            }\n        }\n        return low;\n    }\n}\n\n```
['Dynamic Programming', 'Java']