Python3 DP with explanation
\n\n# Intuition\n\nThe problem is essentially asking for any number, what is the largest consecutive sequence it can form with other larger number\n\nFor exampl
\n\n# Intuition\n\nThe problem is essentially asking for any number, what is the largest consecutive sequence it can form with other **larger** number\n\nFor example:\n\n`[2,1,5,1,1]`\n\nfor `1` it can only **connect** with `2` or `3` (if we increase `1` by 1)\n\nfor `2` it can only **connect** with `3` or `4` (if we increase `2` by 1)\n\nfor `k` it can only **connect** with `k + 1` or `k + 2` (if we increase `k` by 1)\n\n\n\n# Approach\n\nSo the problem now is a DP \n\nfor each number `k` find the max largest consecutive sequence `dp[k]`\n\nand the recursive rules is:\n\n```python\ndp[k] = 1 + dp[k + 1]\ndp[k + 1] = 1 + dp[k + 2]\n```\n\n\n\nwe can first `sort` the array and then do the DP starting from the largest number to smaller number\n\n\n\n# Complexity\n\nTC: Nlog(N)\n\nSC: O(N)\n\n\n\n# Code\n\n```python\nclass Solution:\n    def maxSelectedElements(self, nums: List[int]) -> int:\n        nums.sort()\n        dp = defaultdict(int)\n        global_max = 1\n        for i in range(len(nums) - 1, -1, -1):\n            dp[nums[i]] = 1 + dp[nums[i] + 1]\n            dp[nums[i] + 1] = 1 + dp[nums[i] + 2]\n            global_max = max(global_max, dp[nums[i]], dp[nums[i] + 1])\n\n        return global_max\n```\n\n
['Python3']