Bottom-up Dynamic Programming with 2 state variables
Intuition\n- At each index, we can either increase the value by 1 or not increase the value by 1 and since we cannot solve it greedily, no other choice but to t
# Intuition\n- At each index, we can either increase the value by 1 or not increase the value by 1 and since we cannot solve it greedily, no other choice but to try out all possible combinations.\n\n# Approach\n- We initialize a DP array dp[i][j] where i represents index in the array and j represent whether we decided to increase the value at index i or not.\n    - j=0 signifies we don\'t increase the current index value by 1 and \n    - j=1 signifies we decided to increase the current index value by 1\n    - dp[i][0] signifies the longest consecutive length till index i in nums by deciding not to increase nums[i] (since j=0)\n    - dp[i][1] signifies the longest consecutive length till index i in nums by deciding to increase nums[i] (since j=1)\n- If we can construct the dp array for all i from 0 to n-1 both dp[i][0] and dp[i][1], we are done. We can take maximum of all answers and return.\n- We can see that irrespective whether we consider previous indices or not, dp[i][0]=1 and dp[i][1]=1 since we can only consider current element\n- Now, for any arbitary index i, the values of dp[i][0] and dp[i][1] change based on how the values of nums are present. We will get 3 cases.\n    - nums[i]==nums[i-1]\n        -  j=1 ==> dp[i][1] = 1+dp[i-1][0] (if we have [....11,11] we decided to increase the current value then we should not increment previous index)\n        -  j=0 ==> dp[i][0] = dp[i-1][0] (if we have [....11,11], whatever the value is till [....11] can also be value till [....11,11] since we are dealing with subsequences).\n    - nums[i]==nums[i-1]+1\n        - j=1 ==> dp[i][1] = 1+dp[i-1][1] (assume we have [....,11,12] if we do increment current index, we should also increment previous index)-  \n        - j=0 ==> dp[i][0] = 1+dp[i-1][0] (assume we have [....,11,12] if we do not increment current index, we should also not increment previous index)\n    - nums[i]==nums[i-1]+2\n        - j=0 ==> dp[i][0]=1+dp[i-1][1] (assume we have [....,11,13] if we do not increment current index, we should increment previous index to get continous sequence)\n        \n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)- can be reduced to O(1) since current state only depends on previous state so we can optimize it using 2 variables.\n\n# Code\n```\nclass Solution {\n    public int maxSelectedElements(int[] nums) {\n        Arrays.sort(nums);\n        int n = nums.length;\n        int[][] dp = new int[n][2];\n        dp[0][0]=1;\n        dp[0][1]=1;\n        int ans=1;\n        for(int i=1;i<n;i++){\n            dp[i][0]=1;\n            dp[i][1]=1;\n            if(nums[i]==nums[i-1]){\n                dp[i][0]=dp[i-1][0];\n                dp[i][1]=1+dp[i-1][0];\n            }\n            else if(nums[i]==nums[i-1]+1){\n                dp[i][0]=1+dp[i-1][0];\n                dp[i][1]=1+dp[i-1][1];\n            }\n            else if(nums[i]==nums[i-1]+2)\n                dp[i][0]=1+dp[i-1][1];\n            ans=Math.max(ans,dp[i][0]);\n            ans=Math.max(ans,dp[i][1]);\n        }\n        return ans;\n    }\n}\n```
['Dynamic Programming', 'Java']