题解 | #最大子序列#

/*想获得最大字典序子序列，就要第一次挑字符串中最大字符加入答案，然后从这个字符串下一个位置开始，继续找最大的加入答案；
总结就是让答案中越靠前的字符串越大，同时又要满足答案是子序列；

*/

#include <bits/stdc++.h>
using namespace std;
string ans;

void solve(int index,string s){
    if(index==s.size()){//递归出口，可能性一，最后一个字符为某次递归最大字符，下一次递归后，index为s.size
        return;
    }
    if(index==s.size()-1){//递归出口，可能性二，最后一个字符除了最后只剩自己，它不是任何一次递归最大字符,自己就不和自己比了，直接加进去完事
        ans+=s[index];
        return;
    }
    char max=s[index];
    int idx=index;
    for(int i=index+1;i<s.size();i++){//找到剩余字符中最大的加入答案
        if(max<s[i]){
            max=s[i];
            idx=i;
        }
    }
    ans+=s[idx];
    solve(idx+1,s);//加入最大后，在后面的字符串再找最大的
}


int main() {
    string str;
    cin>>str;
    solve(0,str);
    cout<<ans;
    return 0;

}
// 64 位输出请用 printf("%lld")