字典序最大子序列java_牛客练习赛16 A.字典序最大的子序列(思维)

思路就是既然要找字典序最大的子序列，那就是将最大的先存起来，然后我们如果直接去找最大的字符不好确定它的位置，所以我们需要反着去找，因为最后一个字符肯定是要存起来的，然后再从后往前遍历，将大于等于前一个字符的都存起来就好了。

AC代码：

#include

using namespace std;

string str1,str2;

int main()

{

cin>>str1;

int len = str1.length();

stack q;

for(int i=0;i

q.push(str1[i]);

}

char ch = q.top();

int num = 1;

q.pop();

str2 += ch;

while(!q.empty()){

char ans = q.top();

if(ans >= ch){

ch = ans;

num++;

str2 += ans;

}

q.pop();

}

for(int i=num-1;i>=0;i--){

printf("%c",str2[i]);

}

printf("\n");

return 0;

}

本文同步分享在博客“Ch_zaqdt”(CSDN)。

如有侵权，请联系 support@oschina.cn 删除。

本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。