字典序最大的子序列

Description

给定字符串s，s只包含小写字母，请求出字典序最大的子序列。
子序列：https://en.wikipedia.org/wiki/Subsequence
字典序：https://en.wikipedia.org/wiki/Lexicographical_order

Input

一行一个字符串s (1 <= |s| <= 100,000)。

Output

字典序最大的子序列。

Sample Input

1
ababba

Sample Output

1
bbba

1
abbcbccacbbcbaaba

1
cccccbba

题解：先遍历找出最大字母位置，再从后往前遍历到此位置，取出一个上升子序列。

代码如下：

#include<stdio.h>  
#include<string.h>  
#include<cstring>  
#include<iostream>  
using namespace std;  
char a[1000005];  
int vis[1000005];  
char ans[1000005];  
int main()  
{  
    while(~scanf("%s",a))  
    {  
        int lena=strlen(a);  
        memset(vis,0,sizeof(vis));  
        int maxn=-0x3f3f3f3f;  
        int pos;  
        for(int i=0;i<lena;i++)  
        {  
            vis[i]=a[i]-'0';  
            if(vis[i]>maxn)  
            {  
                maxn=vis[i];  
                pos=i;  
            }  
        }  
        int k=0;  
        int maxn2=-0x3f3f3f3f;  
        for(int i=lena-1;i>=pos;i--)  
        {  
            if(vis[i]>=maxn2)  
            {  

                ans[k++]=a[i];  

                maxn2=vis[i];  

最后

以上就是直率老鼠最近收集整理的关于字典序最大的子序列的全部内容，更多相关字典序最大内容请搜索靠谱客的其他文章。