Sum the max 2 with same digit sum||Beats 100%
IntuitionDivide x in nums into 81 parts according to their digit sums
Find the max of max 2 sum for all parts2 C++ & 1 Python are given.Approach
let digitSum(in
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Divide x in `nums` into 81 parts according to their digit sums
Find the max of max 2 sum for all parts

2 C++ & 1 Python are given.
# Approach
<!-- Describe your approach to solving the problem. -->
1. let `digitSum(int x)` be the function to compute the digit sum for `x`
2. Declare 2D array `int p[82][2]` filled with `{0, 0}` where `p[D]` holds the max 2 elements for all 81 parts with `digitSum(x)=D` (for D=1 to 81). Note that the possible min for `D=digitSum(x)=1` when x=1 & the possible max for `D=digitSum(x)=81` when `x=999999999`.
3. Let `maxD=0, minD=INT_MAX`
4. Transverse all `x in nums` as follows:
```cpp [for x in nums do the following]
int D=digitSum(x);// comupte the digit sum for x store to D
// when first digitsum D seen
if (p[D][0]==0 && p[D][1]==0) 
    p[D][1]=x; // set p[D][1]=x as the max of this part 
// if x>=max(p[D]) 
else if (x>=p[D][1]) 
    p[D][0]=exchange(p[D][1], x);//set (2nd max, 1st max)=(p[D][1], x)
// if x>=2nd max(p[D])
else if (x>=p[D][0]) p[D][0]=x; // set 2nd max(p[D])=x
maxD=max(maxD, D);// update maxD
minD=min(minD, D);// update minD
```
5. let `ans=-1`
6. Using a loop for D=minD to maxD to find `ans=max(ans, p[D][0]+p[D][1])`
7. `ans` is the answer
8. 2nd C++ is the simplifying of the 1st one by using 1D array holding max 1 instead of the 2D array holding max 2; the updating of max for ans is proceeded during the single loop
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n\times \max_{x\in nums}(\log x)+|maxD-minD|)=O(n\times \max_{x\in nums}(\log x)+81)=O(n\times \max_{x\in nums}(\log x))$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(82)=O(1)$
# Code||3ms Beats 98.80%
```cpp []
class Solution {
public:
    static inline int digitSum(int x){
        int sum=0;
        for(; x>0; x/=10){
            sum+=x%10;
        }
        return sum;
    }
    static int maximumSum(vector<int>& nums) {
        int p[82][2]={{0, 0}};
    //    memset(pq, 0, sizeof(pq));
        int maxD=0, minD=INT_MAX;
        for(int x: nums){
            int D=digitSum(x);
            if (p[D][0]==0 && p[D][1]==0) p[D][1]=x;
            else if (x>=p[D][1]) p[D][0]=exchange(p[D][1], x);
            else if (x>=p[D][0]) p[D][0]=x;
            maxD=max(maxD, D);
            minD=min(minD, D);
        }
        
        int ans=-1;
        for(int D=minD; D<=maxD; D++){
            if (p[D][0]==0) continue;
            ans=max(ans, p[D][0]+p[D][1]);
        }
        return ans;
    }
};
auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();  
```
# simple version||C++ 0ms beats 100% & Python
```C++ []
class Solution {
public:
    static inline int digitSum(int x){
        int sum=0;
        for(; x>0; x/=10){
            sum+=x%10;
        }
        return sum;
    }
    static int maximumSum(vector<int>& nums) {
        int maxD[82]={0};
        int ans=-1;
        for(int x: nums){
            int D=digitSum(x);
            if (maxD[D]>0) ans=max(ans, maxD[D]+x);
            maxD[D]=max(maxD[D], x);
        }
        return ans;
    }
};
auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();  
```
```Python []
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def digitSum(x):
            sum=0
            while x>0:
                q, r=divmod(x, 10)
                sum+=r
                x=q
            return sum

        maxD=[0]*82
        ans=-1
        for x in nums:
            D=digitSum(x)
            if maxD[D]>0:
                ans=max(ans, maxD[D]+x)
            maxD[D]=max(maxD[D], x)
        return ans
        
        
```

['Sorting', 'C++', 'Python3']