O(n) time + O(1) Space Solution | C++, Python, Java
IntuitionUse a Hashmap to store the maximum numbers with the same digit sum. In this case since max for this problem is 109, the highest digit sum of any value
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Use a Hashmap to store the maximum numbers with the same digit sum. In this case since max for this problem is $$10^9$$, the highest digit sum of any value is $$81$$ ($$999999999$$) so we can use an array of this size instead.

Iterate through each number. Comput the digit sum of `nums[i]`. If we've seen this digit sum before, update res with the sum of `nums[i]` and `map[num]`. Then update `map[sum]` to hold the maximum number for the digit sum we got.
# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: $$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(1)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int maximumSum(vector<int>& nums) {
        int map[82] = {}, res = -1;
        for (int i = 0; i < nums.size(); i++){
            int sum = 0, num = nums[i];
            while (num > 0){
                sum += (num % 10);
                num /= 10;
            }
            if (map[sum] != 0){
                res = max(res, nums[i] + map[sum]);
                map[sum] = max(map[sum], nums[i]);
            }
            else map[sum] = nums[i];
        }
        return res;
    }
};
```
```python []
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        res = -1
        m = {}
        for num in nums:
            s, n = 0, num
            while n > 0:
                s += n % 10
                n //= 10
            if s in m:
                res = max(res, num + m[s])
                m[s] = max(m[s], num)
            else:
                m[s] = num
        return res
```
```java []
class Solution {
    public int maximumSum(int[] nums) {
        int map[] = new int[82], res = -1;
        for (int i = 0; i < nums.length; i++){
            int sum = 0, num = nums[i];
            while (num > 0){
                sum += (num % 10);
                num /= 10;
            }
            if (map[sum] != 0){
                res = Math.max(res, nums[i] + map[sum]);
                map[sum] = Math.max(map[sum], nums[i]);
            }
            else map[sum] = nums[i];
        }
        return res;
    }
}
```
['Array', 'Hash Table', 'C', 'Sorting', 'Heap (Priority Queue)', 'Python', 'C++', 'Java', 'Python3']