陈利人博客面试题之我解：构造最大数

题目如下：
给定只包含正数的数组，给出一个方法，将数组中的数拼接起来，得到的数，是最大的。 例如： [4, 94, 9, 14, 1] 拼接之后，所得最大数为：9944141

看到这个题目，不知道大家有木有一种似曾相识的感觉，这个最大的排列规则，跟我们查字典的规则是相似的。在字典的排列中，按照首字母的顺序排列，单个字母总是放在字母群的最前面。而这里我们恰好是按照字典序的逆序，如何实现这种字典序的比较呢？
问题，现在就变成了给定两个正数如何实现字典序的比较了？我们将两个正数，变成两个字符串，然后依次比较对应的位置上的值，如果一个字符串长，一个字符串短，我们就要给短的字符串补上该字符串的末尾字符，来得出比较结果。

程序如下：

bool compare(int a, int b)
{
    stringstream ass, bss;
    string as,bs;
    ass << a;
    bss << b;
    ass >> as;
    bss >> bs;
    char *pa = const_cast<char*>(as.c_str());
    char *pb = const_cast<char*>(bs.c_str());
    while(*pa && *pb)
    {
        if(*pa > *pb)
        {
            return true;
        }
        else if(*pa < *pb)
        {
            return false;
        }
        else
        {
            pa++;
            pb++;
        }
    }
    if(*pa)
    {
        if(*pa <= *(--pb))
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    else
    {
        if(*pb <= *(--pa))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

得到了上面的比较方法，我们再来排列源数组，然后输出结果就很容易了：

void getMax2(int *arr, const int size)
{
    sort(&arr[0], &arr[size], compare);
    int i;
    for(i = 0; i < size; i++)
    {
        cout << arr[i];
    }
    cout << endl;
}

ok！大功告成！！