SRM 518 Div2 Medium LargestSubsequence

入力文字列sの部分列の中で最も辞書式順序の大きい部分列を求めよという問題.

長さがxで辞書式順序の一番大きい部分列bとその終了位置のリストwを求める.
長さx+1で辞書式順序の一番大きい部分列はbに一文字足した形になる.
各wの値から付け足せるものを求める.
どんどん繰り返し,候補が一つとなるまで繰り返す.

class LargestSubsequence
{
public:
  int first(string & s, int idx){
    char mc = s[idx];
    int mi = idx;
    for(int i = idx+1; i < s.size(); i++){
      if (mc < s[i]){
        mc = s[i];
        mi = i;
      }
    }
    return mi;
  }
  string getLargest(string s)
    {
      vector<string> m;
      vector<int> idx;
      int n = s.size();
      int i, j;
      int mi = first(s, 0);
      for(i = 0; i < n; i++) if (s[mi] == s[i]){
          m.push_back(s.substr(i,1));
          idx.push_back(i);
      }
      while(m.size() > 1){
        vector<string> next;
        vector<int> idx_next;
        mi = first(s, idx[0]+1);
        if (mi >= n) break;
        idx_next.push_back(mi);
        next.push_back(m[0]+s[mi]);

        for(j = 1; j < m.size(); j++){
          int idx_cur = first(s, idx[j]+1);
          if (idx_cur >= n) break;
          if (s[idx_cur] == s[mi]){
            next.push_back(m[j]+s[idx_cur]);
            idx_next.push_back(idx_cur);
          }
        }
        m = next;
        idx = idx_next;
      }
      mi = first(s, idx[0]+1);
      string ret = m[0];
      while(mi < n){
        ret += s[mi];
        mi = first(s, mi+1);
      }
      return ret;
    }
};