最大子序列

这里我必须要说一个问题，字典序较大，就是两个字符串中比较大的元素，也就是java中compareTo的实现。好吧！我***了，哈哈哈。既然要找最的字典序，肯定要找开头最大。贪心算法，从后往前找，如果前者比后者大，则保留，否则就删除。

public class Main { 
public static void main(String[] args) { 
    Scanner input = new Scanner(System.in); 
    String str = input.nextLine(); 
    char[] res = str.toCharArray(); 
    ArrayList<Character> arr = new ArrayList<>(); 
    arr.add(res[res.length-1]); 
    for (int i = res.length-1; i > 0; i--){ 
        if ( arr.get(arr.size()-1) <= res[i-1]){ 
            arr.add(res[i-1]);             
        }         
    }         
    StringBuilder sb = new StringBuilder();         
    for (int i = 0; i < arr.size(); i++){             
        sb.append(arr.get(i));         
    }         
    System.out.println(sb.reverse().toString());     
    } 
}

分析：从后面找单调递增的不连续序列

console.log(getSeq(line));

"""
@author:liang
"""
def solution(s):
    n=0
    res=[]
    while s != []:
        res.append(max(s))
        n=s.index(max(s))
        s=s[n+1:]
    return "".join(res)
s=raw_input().strip()
s=list(s)
print solution(s)

while(line=readline()){
    var array = line.split("");
    for(var i=array.length-1; i>0; i--){
        if(array[i]>array[i-1]){//如果前一项小于本项
            array.splice(i-1,1)//剔除前一项，确保前面的永远大于后面的
        }
    }
    console.log(array.join(""))
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String in = sc.next();
        int n = in.length();
        TreeMap<Character, Integer> treeMap = new TreeMap<>(new Comparator<Character>() {
            @Override
            public int compare(Character o1, Character o2) {
                return -o1.compareTo(o2);
            }
        });
        char[] inC = in.toCharArray();
        for (int i=0; i<in.length(); i++) {
            if (treeMap.containsKey(inC[i])) {
                treeMap.put(inC[i], treeMap.get(inC[i]) + 1);
            }
            else {
                treeMap.put(inC[i], 1);
            }
        }
        StringBuilder sb = new StringBuilder(); int index = 0;
        for (Map.Entry<Character, Integer> e: treeMap.entrySet()) {
            char c = e.getKey(); int v = e.getValue();
            if (v == 0) { continue; }
            while (index < n && v > 0) {
                if (inC[index] == c) {
                    v--;
                    sb.append(c);
                }
                treeMap.put(inC[index], treeMap.get(inC[index]) -1);
                index++;
            }
        }
        System.out.println(sb.toString());
    }
}

	publicclassMain {



	publicstaticvoidmain(String[] args) {



	Scanner input =newScanner(System.in);



	String str = input.nextLine();



	char[] res = str.toCharArray();



	ArrayList<Character> arr =newArrayList<>();



	arr.add(res[res.length-1]);



	for(inti = res.length-1; i >0; i--){



	if( arr.get(arr.size()-1) <= res[i-1]){



	arr.add(res[i-1]);



	}



	}



	StringBuilder sb =newStringBuilder();



	for(inti =0; i < arr.size(); i++){



	sb.append(arr.get(i));



	}



	System.out.println(sb.reverse().toString());



	}



	}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();

        StringBuilder sb = new StringBuilder();
        char ch = s[s.length - 1];
        for (int i = s.length - 1; i >= 0; i--) {
            if (s[i] >= ch) {
                sb.append(s[i]);
                ch = s[i];
            }
        }
        System.out.println(sb.reverse());
    }
}

#include <iostream>
using namespace std;
#include <string>
#include <algorithm>

int main()
{
    string s, ret;
    cin >> s;
    while (!s.empty())
    {
        auto it = max_element(s.begin(), s.end());
        ret += *it;
        s.erase(s.begin(), it+1);
    }

    cout << ret << endl;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] s = in.next().toCharArray();
        int max = 0;
        while (max < s.length) {  //每次找最大的
            for (int i = max; i < s.length; i++) { //从最大的右侧重新找最大的
                if (s[i] > s[max]) max = i;
            }
            System.out.print(s[max]);
            max++;
        }
    }
}

#include <iostream>
#include <vector>
using namespace std;
//最大递减子序列
int main() {
    string s,res;
    cin>>s;
    char c = s[s.length()-1];
    res += c;
    for(int i=s.length()-2;i>=0;i--)
    {
        if(s[i]>=res[res.length()-1])
        {
            res+=s[i];
        }
    }
    for(int i=res.length()-1;i>=0;i--)
    {
        cout<<res[i];
    }
    cout<<endl;

}

class Solution:
    def solve(self, s):
        """思路：单调递减队列（允许重复）"""
        import collections
        queue = collections.deque()
        for char in s:
            if not queue:
                queue.append(char)
                continue
            while queue and queue[-1] < char:
                queue.pop()
            queue.append(char)
        return ''.join(queue)


if __name__ == "__main__":
    so = Solution()
    s = input()
    print(so.solve(s))


def test():
    so = Solution()
    assert so.solve("test") == "tt"
    assert so.solve("ababba") == "bbba"

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;cin>>s;
    string ans;
    int maxn=0;
    for(int i=s.length()-1;i>0;i--)
        if(s[i-1]<s[i])  s.erase(i-1,1);
    cout<<s<<endl;
}

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {
    string s;
    getline(cin, s, '\n');
    int n = s.size();
    if (n<2) cout << s << endl;
    stack<char> str;
    str.push(s[n-1]);
    for (int i=n-2; i>=0; --i) {
        if (s[i]>=str.top()) str.push(s[i]);
    }
    string res;
    while (!str.empty()) {
        res += str.top();
        str.pop();
    }
    cout << res << endl;
    return 0;
}