simple linear DP solution in c++ with explanation | bottom up dp
firstly update your array in such a way that all elements are sorted and at max two occurrence of each element will be there in array.(this can be done using ma
firstly update your array in such a way that all elements are sorted and at max two occurrence of each element will be there in array.(this can be done using map or simply sorting)\ncreate dp[n][2] where dp[i][0] denotes the longest possible chain including the arr[i] as last element and dp[i][1] denotes the longest possible chain including arr[i]+1 as last element.\nfor transition cases lets take an example: \nfor dp[i][0]:\n[3,4,4,6]\nif we are at index 1 we can see that last value is 3 which is 1 less than current value so we can directly do 1+dp[i-1][0]\nif we are at index 2 we can see that last value is also 4 which is equal to current value so we can copy the previous value dp[i-1][0]\nif we are at index 3 we can see last two values are 4 and 4 and current value is 6 so we can convert last 4 into 5 to create a sequence...in this case 1+dp[i-1][1]\n->dp[i][0] will be the max of all three values..\n\nfor dp[i][1]-\n[3,3,4]\nif we are at index 1 we can see that last value is equal to current value which is 3 so we can convert this 3 into 4... so 1+dp[i-1][0]\nif we are at index 2 current value is 4 and previous value was 3 and we have to convert this 4 into 5 so to make it longer we can also convert previous 3 into 4...\nso the transition will be 1+dp[i-1][1]\n-> dp[i][1] will be the max of these two cases\n\nfinal answer will be the maximum of any intermediate dp[i][0] or dp[i][1]\n\n```\nclass Solution {\npublic:\n    int maxSelectedElements(vector<int>& arr) {\n        \n        \n        map<int,int>mp;\n        for(auto it:arr)\n        {\n            mp[it]++;\n        }\n        vector<int>nums;\n        for(auto it:mp)\n        {\n            if(it.second>=2)\n            {\n                nums.push_back(it.first);\n                nums.push_back(it.first);\n            }\n            else{\n                nums.push_back(it.first);\n            }\n        }\n        int n=nums.size();\n        vector<vector<int>>dp(n+1,vector<int>(2,1));\n        int ans=0;\n        for(int i=0;i<n;i++)\n        {\n            if(i>0)\n            {\n                if(nums[i]==(nums[i-1]+1))\n                {\n                    dp[i][0]=1+dp[i-1][0];\n                }\n                if(nums[i]==nums[i-1])\n                {\n                    dp[i][0]=max(dp[i][0],dp[i-1][0]);\n                }\n                if((nums[i]==(nums[i-1]+2)) && (i>=1))\n                {\n                    dp[i][0]=max(dp[i][0],(1+dp[i-1][1]));\n                }\n                \n            }\n            else{\n                dp[i][0]=1;\n            }\n            if(i>=1)\n            {\n                if(nums[i-1]==nums[i])\n                {\n                    dp[i][1]=1+dp[i-1][0];\n                }\n                if(nums[i-1]==(nums[i]-1))\n                {\n                    dp[i][1]=max(dp[i][1],(1+dp[i-1][1]));\n                }\n            }\n            \n            ans=max(ans,dp[i][0]);\n            ans=max(ans,dp[i][1]);\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C', 'Sorting', 'C++']