Every Transition Explained | | DP + Binary Search
Intuition\n Describe your first thoughts on how to solve this problem.  \n- seeing constrains we know we can carry f(i,something/nothing)\n- Why ,  because O(N)
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. --> \n- seeing constrains we know we can carry f(i,something/nothing)\n- Why ,  because O(N), O(N log N ) or something is only possible .\n- Lets sort this array as order is not important here . \n- And from any element we could move to element which is one more than curr or we could make them so \n- Now lets say Your at particular index i what all different possibility is there \n        1. You start from that index **(state == 2)**\n        2. You came to this point and your not replication (your parent is one less than you ) **(state ==1)**\n        3. You came to this point and your replica (you and your parent is same ) **(state == 0)**\n- So now we could say for any index we have `3 states`\n- Our function will be like `f(index,state)` \n- Now depending upon state where we could move next . Lets see one by one  \n      1. State 2 (Just Started): when You will start from ith index :\n            - Just move forward without doing anything `f(i+1,2)`\n            - You choose ith index and move to next element with same value` f(nextElement with same value:v[i] , 0)`\n            - You choose ith index and move to next element one greater than curr (`v[i]+1`) `f(nextElement with one greater:v[i]+1,1)`\n            - Your increase curr (`v[i]-->v[i]+1`)element and move to next element one greater than curr `f(nextElement with same value:v[i]+1,0)`\n            - Your increase curr (`v[i]-->v[i]+1`)element and move to next element two greater than curr  `f(nextElement with same value:v[i]+2,1)` \n    \n    2. State 1 (Your parent was one smaller than you):\n            - You could move to next element One greater than you (`v[i]+1`) :`f(nextElement one greater :v[i]+1,1)`\n            - You could move to next element with same value (`v[i]`):`f(nextElement with same val:v[i],0)`\n    3. State 0 (Your parent was equal to You): So technically your one greater => v[i] virtually v[i]+1 , so you could v[i]+1 and v[i]+2\n        - move to one greater than curr : `f(next element v[i]+1,0)`\n        - move to two greater than curr : `f(next element v[i]+2,1)`\n        \n- You all we next to do is serach the indexing greater than curr indexing and satisfying the condition `j>i` for that we will use `Binary Search`\n- Look at the `commented code first` \n- Rest is pretty straight forward : Dp , memoizationa and then convert recursive to iteravtive for efficiency . \n- Its Not Easy problem is your not confertable with DP    \n- *THANK YOU hope this helped you*     \n         \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(N*3*3*log(N)) => $$O(NLog(N))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    // int dp[100001][3];\n    int maxSelectedElements(vector<int>& nums) {\n        // memset(dp, -1, sizeof(dp));\n        // memset(dp, 0, sizeof(dp));\n        sort(nums.begin(), nums.end());\n        // int ans = f(0, 2, nums);\n        int ans=f(nums);\n        return ans;\n    }\n    // int f(int i, int state, vector<int>& nums) {\n    //     if (i >= nums.size()) {\n    //         return 0;\n    //     }\n    //     if (dp[i][state] != -1) {\n    //         return dp[i][state];\n    //     }\n    //     int ans = 0, n = nums.size();\n    //     int nextIn =\n    //         lower_bound(nums.begin() + i + 1, nums.end(), nums[i] + 2) -\n    //         nums.begin();\n    //     int nextWIn =\n    //         lower_bound(nums.begin() + i + 1, nums.end(), nums[i] + 1) -\n    //         nums.begin();\n    //     int next = lower_bound(nums.begin() + i + 1, nums.end(), nums[i]) -\n    //                nums.begin();\n    //     nextIn = check(nextIn, nums[i] + 2, n, nums);\n    //     nextWIn = check(nextWIn, nums[i] + 1, n, nums);\n    //     next = check(next, nums[i], n, nums);\n    //     if (state == 2) {\n    //         ans = max(f(i + 1, 2, nums),\n    //                   max(1 + f(next, 0, nums), 1 + f(nextWIn, 1, nums)));\n    //         ans =\n    //             max(ans, max(1 + f(nextWIn, 0, nums), 1 + f(nextIn, 1, nums)));\n    //     } else if (state == 1) {\n    //         ans = max(1 + f(next, 0, nums), 1 + f(nextWIn, 1, nums));\n    //     } else {\n    //         ans = max(1 + f(nextWIn, 0, nums), 1 + f(nextIn, 1, nums));\n    //     }\n    //     return dp[i][state] = ans;\n    // }\n    int f(vector<int>& nums) {\n        int n = nums.size();  \n        vector<vector<int>>dp(n+1,vector<int>(3,0));  \n        for (int i = n - 1; i >= 0; i--) {\n            for (int state = 0; state < 3; state++) {\n                int ans = 0;\n                int nextIn = lower_bound(nums.begin() + i + 1, nums.end(), nums[i] + 2) - nums.begin();\n                int nextWIn = lower_bound(nums.begin() + i + 1, nums.end(), nums[i] + 1) - nums.begin();\n                int next = lower_bound(nums.begin() + i + 1, nums.end(), nums[i]) - nums.begin();\n                nextIn = check(nextIn, nums[i] + 2, n, nums);\n                nextWIn = check(nextWIn, nums[i] + 1, n, nums);\n                next = check(next, nums[i], n, nums);\n                if (state == 2) {\n                    ans = max(dp[i + 1][2], max(1 + dp[next][0], 1 + dp[nextWIn][1]));\n                    ans = max(ans, max(1 + dp[nextWIn][0], 1 + dp[nextIn][1])); // Corrected here\n                } else if (state == 1) {\n                    ans = max(1 + dp[next][0], 1 + dp[nextWIn][1]); // Corrected here\n                } else {\n                    ans = max(1 + dp[nextWIn][0], 1 + dp[nextIn][1]); // Corrected here\n                }\n                dp[i][state] = ans;\n            }\n        }\n        return dp[0][2];\n    }\n    int check(int ind, int num, int n, vector<int>& v) {\n        if ((ind >= n) || v[ind] != num) {\n            return n;\n        }\n        return ind;\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'C++']