DP | C++ | Simple
Intuition\n Describe your first thoughts on how to solve this problem. \nTo maximize the number of selected elements, we can iterate through the sorted array an
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo maximize the number of selected elements, we can iterate through the sorted array and keep track of the maximum number of selected elements ending at each position.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort the input array in ascending order.\n2. Create a dynamic programming (DP) table to store the maximum number of selected elements ending at each number.\n3. Iterate through each number in the sorted array.\n4. For each number, update the DP table to account for selecting the current number or skipping it.\n5. Keep track of the maximum number of selected elements seen so far.\n6. Return the maximum number of selected elements.\n\n# Complexity\n- Time complexity:\n  - Sorting the array takes $$O(n \\log n)$$ time.\n  - Iterating through the array and updating the DP table takes $$O(n)$$ time.\n  - Therefore, the overall time complexity is $$O(n \\log n)$$.\n- Space complexity:\n  - We use a DP table of size $$O(n)$$.\n  - Sorting the array requires additional space of $$O(n)$$.\n  - Hence, the overall space complexity is $$O(n)$$.\n\n# Code\n```\nclass Solution {\npublic:\n    int maxSelectedElements(vector<int>& nums) {\n        sort(nums.begin() , nums.end());\n        unordered_map<int,int> dp;\n        int ans = 0;\n        for(auto it : nums){\n            dp[it+1] = dp[it] + 1;\n            dp[it] = dp[it-1]+1;\n            ans = max({ans,dp[it+1], dp[it]});\n        }\n        return ans;\n    }\n};\n```
['C++']