PYTHON || Runtime 551 ms Beats 99.46% of users with Python3
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks to find the maximum number of selected elements in an array with the c
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks to find the maximum number of selected elements in an array with the constraint that no two selected elements should have a difference greater than 1. The intuition is to sort the array and then iterate through it to find the maximum number of consecutive elements, ensuring that the difference between any two selected elements is at most 1.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the array to arrange elements in ascending order.\nInitialize variables: ans to store the maximum number of selected elements, prev to keep track of the previous element, prev_max to store the length of the current consecutive sequence, and prev_max_1 to store the length of the previous consecutive sequence.\nIterate through the sorted array:\nIf the current element is equal to the previous element, update prev_max_1 and ans.\nIf the difference between the current element and the previous one is greater than 2, reset both prev_max and prev_max_1 to 1.\nIf the current element is one more than the previous one, update prev_max and prev_max_1 and update ans accordingly.\nIf the current element is not consecutive, update prev_max and reset prev_max_1 to 1.\nReturn the maximum number of selected elements stored in ans.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlogn), where n is the length of the nums array. The sorting step dominates the time complexity.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1), as the algorithm uses only a constant amount of extra space.\n\n# Code\n```\nclass Solution:\n    def maxSelectedElements(self, nums: List[int]) -> int:\n        nums.sort()\n        ans, prev = 1, -inf\n        prev_max = prev_max_1 = 1\n        for x in nums:\n            if x == prev:\n                prev_max_1 = prev_max + 1\n                ans = max(ans, prev_max_1)\n                continue\n            if x - prev > 2:\n                prev_max = prev_max_1 = 1\n            elif x == prev + 1:\n                prev_max, prev_max_1 = prev_max + 1, prev_max_1 + 1\n                ans = max(ans, prev_max, prev_max_1)\n            else:\n                prev_max, prev_max_1 = prev_max_1 + 1, 1\n                ans = max(ans, prev_max)\n            prev = x\n        return ans\n\n        \n```
['Array', 'Dynamic Programming', 'Greedy', 'Memoization', 'Sorting', 'Python', 'Python3']