[Java] ✨✨✨ (Explained!) Dynamic Programming solution
Intuition and Approach\nLet\'s look attentively to the problem and try to simplify it for us.\nWe have multiple numbers, they may be either the same, or differe
# Intuition and Approach\nLet\'s look attentively to the problem and try to simplify it for us.\nWe have multiple numbers, they may be either the same, or different, we don\'t know this. For each number we literally can do just 2 operations:\n- Leave as is;\n- Increment by 1;\nThe first observation is that **we don\'t need more than 2 copies of each number**. Why? Because of 1 of the copies of any x we can leave it as x, and for another make it x+1. We can\'t do anything else to this x, and duplicates of x can\'t participate in the chain (as numbers must be consequative).\n\nSo we can transform original array nums to a smaller one by removing all duplicates and leave maximum 2 copies of each value.\n\nNext, we should sort the resulted array ascending.\n\nNow, it\'s going to be a Dynamic Programming with 2 parameters:\n- Index of the number;\n- Mode - or we can call it incrementor. If it\'s 0, we don\'t change the value, if 1 - we\'re adding 1.\n\nFor each number at index i we do the following:\n- check the mode/incrementor and adjust the number in our calculations;\n- check whether (i+1)th number differs from our adjusted number by 1. If so, then we update the result of i-th number for the given mode/incrementor:\n$$dp[i][mode] = max(dp[i][mode], 1 + dp(i+1, 0))$$\n- check whether (i+1)th number is equal to our adjusted number. If so, then we update the result of i-th number for the given mode/incrementor:\n$$dp[i][mode] = max(dp[i][mode], 1 + dp(i+1, 1))$$\n- **Attention!** We do the same checks as above - with (i+2)-th and (i+3)-th numbers! Why? Let\'s see what chains we can have:\n.... x, x, x+1, x+1, ...\n.... x, x, x+1, x+2 ...\n.... x, x+1, x+1, x+2....\n.... x, x+2, x+2, x+3....\nand etc....\nAs we have just 2 copies of each value, there is no point to check (i+4)-th and further numbers - as the difference will always be more than 1.\nAt the same time, we may want to build a sequence not with the neighbour (i+1), but with further numbers - so that we don\'t increment them by 1 for example and don\'t break further chains... Simply put, dp[i+1][mode_1] and dp[i+2][mode_2] and dp[i+3][mode_3] may produce quite different results and not always the former ones are better.\n- We go with DP till the (n-1)-th element. For this element the max chain is always 1 (just (n-1)th number, or this number incremented by 1, depending on the mode).\n\nNow, as we have our DP calculated, we should **run a loop for i from 0 to n-1** , where i is the starting element of the chain.\nThis loop won\'t spoil our time complexity, because we\'ll use the same DP array.\nThe result is the max possible value.\n\n# Complexity\n- Time complexity:\n$$O(n log)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n\n  int max = 0;\n  int[][] dp;\n  int n;\n\n  public int maxSelectedElements(int[] nums) {\n    Map<Integer, Integer> counts = new HashMap<>();\n    for (int num : nums) {\n      if (counts.getOrDefault(num, 0) < 2) {\n        counts.put(num, counts.getOrDefault(num, 0) + 1);\n      }\n    }\n    List<Integer> nums2 = new ArrayList<>();\n    for (int num : counts.keySet()) {\n      for (int i = 0; i < counts.get(num); i++) {\n        nums2.add(num);\n      }\n    }\n    int[] nums3 = new int[nums2.size()];\n    for (int i = 0; i < nums2.size(); i++) {\n      nums3[i] = nums2.get(i);\n    }\n    Arrays.sort(nums3);\n    n = nums3.length;\n    dp = new int[n][2];\n    for (int i = 0; i < n; i++) {\n      dp[i][0] = -1;\n      dp[i][1] = -1;\n    }\n    int res = 0;\n    for (int i = 0; i < n; i++) {\n      res = Math.max(res, dp(nums3, i, 0));\n      res = Math.max(res, dp(nums3, i, 1));\n    }\n    return res;\n  }\n\n  private int dp(int[] nums, int i, int mode) {\n    if (i == n) {\n      return 0;\n    }\n    if (dp[i][mode] != -1) {\n      return dp[i][mode];\n    }\n    if (i == n - 1) {\n      return dp[i][mode] = 1;\n    }\n    int curr = nums[i];\n    if (mode == 1) {\n      curr++;\n    }\n    int res = 1;\n    for (int j = i + 1; j <= i + 3 && j < n; j++) {\n        if (nums[j] == curr) {\n            res = Math.max(res, 1 + dp(nums, j, 1));\n        }\n      if (nums[j] == curr + 1) {\n        res = Math.max(res, 1 + dp(nums, j, 0));\n      }\n    }\n    return dp[i][mode] = res;\n  }\n}\n```
['Java']