SRM518 Div1Easy LargestSubsequence

問題URL：LargestSubsequence
最長増加部分列(LIS)が連想されたけどそうでもなかった。
ひさびさに瞬殺できる問題が来てうれしい。

考察

サンプル2:exampleの部分文字列で辞書順最大を考える。
この中で一番大きいのはxだから、まずxが確定。次に取るべきはxより右の文字列ampleの中で最大のもの(左から取ったら明らかに小さくなる)。この中の最大はpだからxpが確定して…とやるとxpleが答え。こんな感じで、前に取った文字よりも右側の文字のうち最大となるものを取るといい。複数あったら一番左。

実装

exampleを後ろから順に大小評価するとxxppleという文字列ができる。これは「自分とそれより右側で最大の文字」を表す。すると後は元の文字列とのdiffを取るだけでよい。

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

class LargestSubsequence {
public:
    string getLargest( string s ){
        int n=s.size();
        string t=s;
        for(int i=n-2;i>=0;i--){
            t[i]=max(t[i],t[i+1]);
        }
        string ans;
        for(int i=0;i<n;i++){
            if(s[i]==t[i]) ans+=s[i];
        }
        return ans;
    }
};