DP | Cleanest Code | Explained
Intuition\nTry to think in terms of What could be the longest subsequence ending at a number?\n\n# Approach\n1. Sort the array, because longest valid sequence e
# Intuition\nTry to think in terms of `What could be the longest subsequence ending at a number?`\n\n# Approach\n1. Sort the array, because longest valid sequence ending at a num is depenedent on num-1.\n2. Since nums[i]<=1e6, we can make a dp array of 1e6, where indices reperesent elements of nums (If elements were large we could\'ve used a hashmap as our dp array).\n3. Since an element(num) can act as both num and num+1, first consider it as num+1 and if there is a valid sequence ending at num, it\'ll automatically be considered by recurrence `dp[num+1]=dp[num]+1`. \n4. Now do same for num i.e. `dp[num]=dp[num-1]+1`. Maximum of this do array is the answer. (Since it represents maximum sequence ending at that number).\n\n# Complexity\n- Time Complexity: O(max_element) \n- Space Complexity: O(max_element)\n\n\n# Code\n```\nint maxSelectedElements(vector<int>& nums) {\n    sort(begin(nums),end(nums));\n    vector <int> dp(1000002,0);\n    for(auto num:nums) {\n        dp[num+1]=1+dp[num];\n        dp[num]=max(dp[num],1+dp[num-1]);\n    }\n    return *max_element(begin(dp),end(dp));\n}\n```
['Dynamic Programming', 'C++']