[100% <70ms] Detailed explanation | Sort + Simplified DP | Improved Space O(1)
Motivation\nI solve this problem in a virtual contest with a improved DP approach (or it can be regarded as greedy). The results show that both time and space c
**Motivation**\nI solve this problem in a virtual contest with a improved DP approach (or it can be regarded as greedy). The results show that both time and space complexity beating 100%. Meanwhile, I don\'t think existing solutions showing the interesting O(1) space complexity.\n\n**Approach**\nLet us begin with the natations. As used in some other solutions, we define  `DP[val]` as the length of the longest array of element starting with `val`, i.e. there should be an array `val, val+1, ..., val+DP[val]-1`. This is a two stage2 solution.\n\n* Stage 1: sort the list of numbers\n* Stage 2: scan backwards step by step. Suppose the element currently scanned is **val=nums[i]** and we actually have two options\n\t* Option 1: Keep the value of `val` unchanged, s.t. `DP[val]=max(DP[val], 1+DP[val+1])`\n\t* Option 2: Increase the value of `val` by 1, s.t. `DP[val+1]=max(DP[val+1], 1+DP[val+2])`\n\n***Improved Space*:**\tPlease be awared of  `DP[val]` and `DP[val+1]`, which are the only two we can update in each step of **Stage 2**. It sounds harmless to store `DP[val]` in **dp[0]** and `DP[val+1]` in **dp[1]**. Meanwhile, remember that we have sorted the numbers in the first stage. According to the difference between the adjacent elements (**delta=nums[i+1]-nums[i]**), there are four cases:\n* Case 1: `delta=0`, `val=nums[i]=nums[i+1]`:\n\t* We have the chance to update `DP[val]` by **keeping `nums[i]` unchanged and increasing `nums[i+1]` by 1**. Given that `DP[val]` is `dp[0]` and `DP[val+1]` is `dp[1]`, `DP[val]=max(DP[val], 1+DP[val+1])` can be expressed as **`dp[0]=max(dp[0], 1+dp[1])`**.\n* Case 2: `delta=1`, \'val=nums[i]=nums[i+1]-1\':\n\t* We have the chance to update `DP[val+1]` by **increasing both `nums[i]` and `nums[i+1]` by 1**. Given that `DP[val+1]` is `dp[0]` and `DP[val+2]` is `dp[1]`, `DP[val+1]=max(DP[val+1], 1+DP[val+2])` can be expressed as **`dp[1]=max(dp[0], 1+dp[1])`**.\n\t* We have the chance to update `DP[val]` by **keeping both `nums[i]` and `nums[i+1]` unchanged**. Given that `DP[val]=1` and `DP[val+1]` is `dp[0]` and `DP[val+2]` is `dp[1]`, `DP[val]=max(DP[val], 1+DP[val+1])=1+DP[val+1]` can be expressed as **`dp[0]=1+dp[0]`**.\n* Case 3: `delta=2`, \'val=nums[i]=nums[i+1]-2\':\n\t* We have the chance to update `DP[val+1]` by **increasing both `nums[i]` by 1 and keeping `nums[i+1]` unchanged**. Given that `DP[val]=DP[val+1]=1` and `DP[val+2]` is `dp[0]` and `DP[val+3]` is `dp[1]`, `DP[val+1]=max(DP[val+1], 1+DP[val+2])=1+DP[val+2]` can be expressed as **`dp[1]=1+dp[0]`**.\n* Case 4: `delta>2`\n\t* We have no chance to combine `nums[i]` and `nums[i+1]` and **`dp[0]=dp[1]=1`**.\n\nNow, we reduce the space complexity to **O(1)** as promised.\n\n**Complexity**\n* Time Complexity: **O(nlogn)** w.r.t. sorting\n* Space Complexity: **O(1)** w.r.t. improved DP.\n```\nRuntime: 69 ms, faster than 100.00% of C++ online submissions for Maximize Consecutive Elements in an Array After Modification.\nMemory Usage: 74.4 MB, less than 100.00% of C++ online submissions for Maximize Consecutive Elements in an Array After Modification.\n```\n**Code**\n```\nint dp[2];\nclass Solution {\npublic:\n    int maxSelectedElements(vector<int>& nums) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n        int ans=1;\n        sort(nums.begin(), nums.end());\n        dp[0]=dp[1]=1;\n        for(int i=nums.size()-2; i>=0; --i) {\n            switch(nums[i+1]-nums[i]) {\n                case 0:\n                    ans=max(ans, dp[0]=max(dp[0], dp[1]+1));\n                    break;\n                case 1:\n                    ans=max(ans, dp[1]=max(dp[0], dp[1]+1));\n                    ans=max(ans, dp[0]+=1);\n                    break;\n                case 2:\n                    ans=max(ans, dp[1]=dp[0]+1);\n                    dp[0]=1;                    \n                    break;\n                default:\n                    dp[0]=dp[1]=1;\n                    break;\n            }\n        }\n        return ans;\n    }\n};\n```
['Greedy']