c++ easy dp
Intuition\n1. a sequence can start from any number of the array\n2. there are 2 option  on each number , increase it value by +1 or remain same\n\n# Approach\ni
# Intuition\n1. a sequence can start from any number of the array\n2. there are 2 option  on each number , increase it value by +1 or remain same\n\n# Approach\ninc == 1 \n-> previous number i-1 was increase by 1\nince == 0\n-> previous number i-1 was not increase \n\nfor inc == 1 \n\nnums[i]==nums[i-1]+1.  --> eg both i ,i-1 are to be increased by 1 to continue the sequence\nnums[i]==nums[i-1]+2.  --> only i-1 was increase by one to continue 3the sequnce\nnums[i]==nums[i-1].  --> eg {12,12,12,12,14}\n\nwe convert this to {12,13,13,13,14} \n\n\nfor inc ==0\nnums[i]==nums[i-1]+1 non is increased\n\nnums[i]==nums[i-1]  i need to be increase by 1\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(n);\n\n# Code\n```\nclass Solution {\npublic:\n    int dp[100001][2];\n    int solver(vector<int>&nums,int n, int i, int inc)\n    {\n        if(i==n)\n        return 0;\n       \n       if(dp[i][inc]!=-1)\n       return dp[i][inc];\n\n        int ans = 0;\n        if(inc==1)\n        {\n            if(nums[i]==nums[i-1]+1)\n             ans = max(ans,solver(nums,n,i+1,1)+1);\n\n           else if(nums[i]==nums[i-1]+2)\n             ans = max(ans,solver(nums,n,i+1,0)+1);\n            \n            else if(nums[i]==nums[i-1])\n              ans = max(ans,solver(nums,n,i+1,1));\n        }\n        else\n        {\n            if(nums[i]==nums[i-1]+1)\n             ans = max(ans,solver(nums,n,i+1,0)+1);\n\n            else if(nums[i]==nums[i-1])\n             ans = max(ans,solver(nums,n,i+1,1)+1);\n        }\n        return dp[i][inc] = ans;\n    }\n    int maxSelectedElements(vector<int>& nums) {\n       int n=nums.size();\n       sort(nums.begin(),nums.end());\n\n        int ans=1;\n        memset(dp,-1,sizeof(dp));\n        for(int i=1;i<n;i++)\n        ans = max(ans,max(solver(nums,n,i,0),solver(nums,n,i,1))+1);  \n\n        return ans; \n    }\n};\n```
['Dynamic Programming', 'C++']