Java DP Bottom Up with a lot comments O(1) space
Did this bottom up during contest, but realized this can be optimized with space O(1). So here it is:\n\n\nclass Solution {\n    public int maxSelectedElements(
Did this bottom up during contest, but realized this can be optimized with space O(1). So here it is:\n\n```\nclass Solution {\n    public int maxSelectedElements(int[] nums) {\n        \n        // Time O(NlogN), Space O(N)\n        Arrays.sort(nums);\n        int N = nums.length, res = 1;\n        int prev = 1, prevPlus = 1; \n        // prev stands for the max length of consecutive numbers without incrementing number at i\n        // prevPlus means curr num is incremented by 1 already\n        \n        /* after sorting 1,1,1,2,5 => 1,1,2,3,5 */\n        for(int i = 1; i < N; i++) {\n            int curr = 1, currPlus = 1;\n            if(nums[i] - nums[i - 1] > 2) {\n                // when the diff is too large, reset\n                // current i is counted as 1\n                curr = currPlus = 1;\n            } else if(nums[i] - nums[i - 1] == 2) {\n                // when the diff is exactly 2, it\'s only consecutive for dp[i][0] if previous num is already incremented.\n                // And dp[i][1] has to be reset to 1 since after incrementing curr number, there is no way to have consecutive list.\n                curr = prevPlus + 1;\n                currPlus = 1;\n            } else if(nums[i] - nums[i - 1] == 0) {\n                // This is actually the tricky part, when two numbers are the same, we don\'t want to reset here, since\n                // what had been accumulated as consecutive array is still useful. We carry over same result for not-increment.\n                // And if we increment num at i, we actually make existing list at dp[i - 1][0] even longer.\n                curr = prev;\n                currPlus = Math.max(prev + 1, prevPlus);                    \n            } else {\n                // This is the easy part, when nums[i] - nums[i - 1] == 1, we simply add one.\n                curr = prev + 1;\n                currPlus = prevPlus + 1;\n            }\n            \n            // we have to check res for each number since the max length may appear in the middle.\n            res = Math.max(res, Math.max(curr, currPlus));\n            prev = curr; prevPlus = currPlus;\n        }\n        return res;\n    }\n}\n```\n\n# Code with O(N) space.\n```\nclass Solution {\n    public int maxSelectedElements(int[] nums) {\n        \n        // Time O(NlogN), Space O(N)\n        Arrays.sort(nums);\n        int N = nums.length, res = 1;\n        int[][] dp = new int[N][2];\n        dp[0][0] = 1; dp[0][1] = 1; \n        // [i][0] stands for the max length of consecutive numbers without incrementing number at i\n        // [i][1] means curr num is incremented by 1 already\n        \n        /* after sorting 1,1,1,2,5 => 1,1,2,3,5 */\n\n        for(int i = 1; i < N; i++) {\n            if(nums[i] - nums[i - 1] > 2) {\n                // when the diff is too large, reset\n                // current i is counted as 1\n                dp[i][0] = dp[i][1] = 1; \n                continue;\n            } else if(nums[i] - nums[i - 1] == 2) {\n                // when the diff is exactly 2, it\'s only consecutive for dp[i][0] if previous num is already incremented.\n                // And dp[i][1] has to be reset to 1 since after incrementing curr number, there is no way to have consecutive list.\n                dp[i][0] = dp[i - 1][1] + 1;\n                dp[i][1] = 1;\n            } else if(nums[i] - nums[i - 1] == 0) {\n                // This is actually the tricky part, when two numbers are the same, we don\'t want to reset here, since\n                // what had been accumulated as consecutive array is still useful. We carry over same result for not-increment.\n                // And if we increment num at i, we actually make existing list at dp[i - 1][0] even longer.\n                dp[i][0] = dp[i - 1][0];\n                dp[i][1] = Math.max(dp[i - 1][0] + 1, dp[i - 1][1]);                    \n            } else {\n                // This is the easy part, when nums[i] - nums[i - 1] == 1, we simply add one.\n                dp[i][0] = dp[i - 1][0] + 1;\n                dp[i][1] = dp[i - 1][1] + 1;                \n                \n            }\n            \n            // we have to check res for each number since the max length may appear in the middle.\n            res = Math.max(res, Math.max(dp[i][0], dp[i][1]));\n        }\n        \n        //System.out.println(Arrays.deepToString(dp));\n        // final dp looks like:\n        // [[1, 1], [1, 2], [1, 2], [2, 3], [1, 1]]\n        return res;\n    }\n}\n```
['Java']