[Java/C++/Python] DP
Intuition\nSort input A first.\n\n\n# Solution 1: DP\n\ndp[a] is the maximum length of consecutive sequence ending with a.\n\nIterates through each a in the sor
# **Intuition**\nSort input `A` first.\n<br>\n\n# **Solution 1: DP**\n\n`dp[a]` is the maximum length of consecutive sequence ending with `a`.\n\nIterates through each `a` in the sorted `A`.\nWe can use `a` as `a + 1`, so we update `dp[a + 1] = dp[a] + 1`\nWe can use `a` as `a` itself, so we update `dp[a] = dp[a - 1] + 1`\n\nFinally we return the max length in `dp` values.\n\nTime `O(sort) + O(n)`\nSpace `O(sort) + O(n)`\n\n\n**Java**\n```java\n    public int maxSelectedElements(int[] A) {\n        HashMap<Integer, Integer> dp = new HashMap<>();\n        Arrays.sort(A);\n        int res = 0;\n        for (int a : A) {\n            dp.put(a + 1, dp.getOrDefault(a, 0) + 1);\n            dp.put(a, dp.getOrDefault(a - 1, 0) + 1);\n            res = Math.max(res, Math.max(dp.get(a), dp.get(a + 1)));\n        }\n        return res;\n    }\n```\n\n**C++**\n```cpp\n    int maxSelectedElements(vector<int>& A) {\n        unordered_map<int, int> dp;\n        sort(A.begin(), A.end());\n        int res = 0;\n        for (int& a : A) {\n            res = max(res, dp[a + 1] = dp[a] + 1);\n            res = max(res, dp[a] = dp[a - 1] + 1);\n        }\n        return res;\n    }\n```\n\n**Python**\n```py\n    def maxSelectedElements(self, A: List[int]) -> int:\n        dp = defaultdict(int)\n        A.sort()\n        for a in A:\n            dp[a + 1] = dp[a] + 1\n            dp[a] = dp[a - 1] + 1\n        return max(dp.values())\n```\n<br>\n\n# **Solution 2: O(1) Space**\nSame as Solution 1, but save the space of `dp`\n\n**Java**\n```java\n    public int maxSelectedElements(int[] A) {\n        Arrays.sort(A);\n        int pre = -10, res = 1, c1 = 1, c2 = 1;\n        for (int a : A) {\n            if (a == pre) {\n                c2 = c1 + 1;\n            } else if (a == pre + 1) {\n                c1++;\n                c2++;\n            } else if (a == pre + 2) {\n                c1 = c2 + 1;\n                c2 = 1;\n            } else {\n                c1 = c2 = 1;\n            }\n            res = Math.max(res, Math.max(c1, c2));\n            pre = a;\n        }\n        return res;\n    }\n```\n\n**C++**\n```cpp\n    int maxSelectedElements(vector<int>& A) {\n        sort(A.begin(), A.end());\n        int pre = -10, res = 1, c1 = 1, c2 = 1;\n        for (int& a : A) {\n            if (a == pre) {\n                c2 = c1 + 1;\n            } else if (a == pre + 1) {\n                c1++;\n                c2++;\n            } else if (a == pre + 2) {\n                c1 = c2 + 1;\n                c2 = 1;\n            } else {\n                c1 = c2 = 1;\n            }\n            res = max(res, max(c1, c2));\n            pre = a;\n        }\n        return res;\n    }\n```\n\n**Python**\n```py\n    def maxSelectedElements(self, A: List[int]) -> int:\n        A.sort()\n        pre = -10\n        res = c1 = c2 = 1\n        for a in A:\n            if a == pre:\n                c2 = c1 + 1\n            elif a == pre + 1:\n                c1, c2 = c1 + 1, c2 + 1\n            elif a == pre + 2:\n                c1, c2 = c2 + 1, 1\n            else:\n                c1 = c2 = 1\n            res = max(res, c1, c2)\n            pre = a\n        return res\n```\n\nTime `O(sort) + O(n)`\nSpace `O(sort) + O(1)`\n
['C', 'Python', 'Java']