2801 字符串重组 1≤N≤10000000

Question

现在有一个长度为N的字符串，全部由大写字母组成，每次可以从字符串的开头或者结尾挑选一个字符，加到一个新字符串后面，新字符串初始是空串，被挑选的字符要在原串里删除。要使最终的新字符串字典序最大，求出这个字典序最大的新字符串。

字典序是单词按字母顺序排列的方法。例如，“B"的字典序大于"A”；“ABD"的字典序大于"ABC”

Answer 1

算法比较简单，比较字符串开头和结尾的字符，把大的复制到新字符串，并且从旧的删除，然后继续重复上面步骤，知道字符串为空。
是这个意思吧？

#include <iostream>
#include <time.h>

using namespace std;

int N;
char* initstr()
{
    cout << "输入字符串长度：" << endl;
    cin >> N;
    char *s=new char[N];
    srand((unsigned)time(NULL));
    for(int i=0;i<N;i++)
    {
        s[i]=(char)((rand()%26)+'A');
    }    
    s[N]='\0';
    return s;    
}

int main()
{
    char *str;
    str=initstr();
    cout << str << endl;

    char *str2=new char[N];
    int k=0;

    while(N>0)
    {
        if(*str>=str[N-1])
        {
            str2[k]=*str;
            str++;
        }
        else
        {
            str2[k]=str[N-1];
            str[N-1]='\0';
        }        
        N--;
        k++;
    }

    cout << str2 << endl;

    return 0;
}