Hard ?? Easy DP solution | C++
IntuitionThe problem asks us to maximize the size of a subsequence from the array where all the elements are consecutive integers. Since we can increase each el
# Intuition
The problem asks us to maximize the size of a subsequence from the array where all the elements are consecutive integers. Since we can increase each element by at most 1, it gives us the flexibility to adjust the range of consecutive numbers we can achieve.

Key ideas:
The ability to increase elements means that for a number x in the array, it can become either x or x + 1.
To maximize the length of a valid subsequence, we need to account for these possible adjustments while ensuring that the subsequence remains consecutive.
Dynamic Programming (DP) is suitable since each number in the array can depend on the maximum subsequences formed by previous numbers.
# Approach
1. ### Sort the array:
    Sorting ensures that we process the numbers in increasing order, which is necessary to check consecutive sequences.
2. ### Use a map for DP:
    Let dp[x] represent the maximum number of consecutive elements ending at x.
    For each number x in the array:
    If x becomes itself, update dp[x] as 1 + dp[x - 1].
    If x is incremented to x + 1, update dp[x + 1] as 1 + dp[x] (considering the previous value of x).

3. ### Iterate through the array:
    For each number, calculate the possible updates to dp and keep track of the maximum length of consecutive elements.

4. ### Return the maximum value in dp:
This gives the largest number of consecutive elements that can be selected.

# Complexity
- Time complexity:
O(nlogn) - sorting

- Space complexity:
O(n) - map<int,int>

# Code
```cpp []
class Solution {
public:
    int maxSelectedElements(vector<int>& nums) {
        map<int, int> dp; // Map to store maximum subsequence length ending at x
        int n = nums.size(), ans = 0;

        // Step 1: Sort the array
        sort(nums.begin(), nums.end());

        // Step 2: Process each number
        for (int i = 0; i < n; i++) {
            int x = nums[i], prev = dp[x];
            
            // Update dp[x] for taking x as is
            dp[x] = max(dp[x], 1 + dp[x - 1]);
            
            // Update dp[x + 1] for incrementing x by 1
            // since dp[x] changing we take its prev value instead of new dp[x]
            dp[x + 1] = max(dp[x + 1], 1 + prev);

            // Track the maximum answer
            ans = max({ans, dp[x], dp[x + 1]});
        }

        return ans;
    }
};


```
['Dynamic Programming', 'C++']