20分解法

由于n只有5，直接暴力枚举或者爆搜即可，时间复杂度o（n^n），空间复杂度o（1）

50分解法

贪心思想，不难想到应该令k-1个数一位，1个数n-k+1位。之后，因为越大的数作为高位对和贡献越大，所以将字符串里的元素从大到小排序一下
，再将前n-k+1位作为第1个数，剩下k-1位作为剩下k-1个数，加出来的和即为最大值。由于加法是大数相加，所以要用到高精度。一般的高精度一次相加时间复杂度为o（n），所以加k-1次，时间复杂度为o（nk）,空间复杂度为o（n）。

100分解法

其实就是在50分做法上做一些优化，虽然正常的高精度加法一次是o（n）的，但是我们的加法很特殊，因为每次都只加一个1位数，1位数一次最多只能+9，所以加k-1次平均每次的进位数是很少的，我们只需要加到不再进位了就不用再加了，均摊下来每次加法时间复杂度o（1），所以总的时间复杂度o(n)。当然如果觉得魔改高精度模板比较复杂这里提供另一种做法。因为有k-1个1位数，我们可以先将这k-1个数加一起，把和转换成字符串与之前的n-k+1位的字符串进行高精度相加。这样只需要进行一次高精度加法，时间复杂度也为o（n）。当然排序那里也需要耗费时间，如果直接sort的话时间复杂度为o（nlogn），当然也可以开个a[10]记录一下1-9每个数出现的次数，这样的话排序的时间复杂度为o（n），上述做法的空间复杂度都为o（n），不论哪一种做法都可以通过本题，下面是代码：
ps：时间比较宽裕的开了c++标程的近3倍,但是java字符串和大数类操作都是挺慢的，虽然没有刻意卡java但是java很难通过。如果想java通过本题可能要更加注意一下字符串的操作是否足够快并且手写高精度了，我用封装的类（BigInteger）测试时是会超时的，还是旨在考察手写高精度这样基础算法的功底的，手写的比封装的类还是能快特别多的。

bool cmp(char a,char b)
{
    return a>b;
}

class Solution {
public:
    /**
     * 返回最大和的字符串
     * @param x string字符串 即题目描述中所给字符串
     * @param k int整型 即题目描述中所给的k
     * @return string字符串
     */
    string intToString(int num) {
        stringstream ss;
        ss<<num;
        return ss.str();
    }
    string add(string s1, string s2){
        string ans;
        int len1 = s1.length() - 1;
        int len2 = s2.length() - 1;
        int s = 0;
        int re = 0;
        while (len1 >= 0 || len2 >= 0)
        {
            s = re;
            if (len1 >= 0)
            s += s1[len1] - '0';
            if (len2 >= 0)
            s += s2[len2] - '0';
            re = s / 10;
            ans.push_back(s % 10 + '0');
            len1--;
            len2--;
         }
        if (re)
            ans.push_back(re + '0');
        reverse(ans.begin(), ans.end());
        return ans;
    }
    string Maxsumforknumers(string x, int k) {
        // write code here
        int n=x.size();
        sort(x.begin(),x.end(),cmp);
        int sum=0;
        int m=n-k+1;
        string str=x.substr(0,m);
        for(int i=m;i<n;i++)sum+=x[i]-'0';
        string str2=intToString(sum);
        str=add(str,str2);
        return str;
    }
};