字典序最大的子序列

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

ababba

Sample Output

bbba

abbcbccacbbcbaaba

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];  

最后

以上就是直率老鼠为你收集整理的字典序最大的子序列的全部内容，希望文章能够帮你解决字典序最大的子序列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。