每天一道面试题（三）
（木瓜移动.2013）给定一个字符串，求串中字典序最大的子序列
解析：本题是一道ACM入门题目。思路如下
字典序最大的子序列是这样构造的：设字符串为a0a1.....an-1。首先在a0a1.....an-1找到值最大的字符ai，然后在剩余的ai+1....an-1中值最大的字符aj，然后在剩余的aj+1....an-1中 值最大的字符ak.....直到字符串的长度为0。则aiajak...即为答案
容易想到，an-1一定在所求串中，因此一个好的方法就是从an-1开始向前搜索，当当前值大于或等于子序列中首字符的值时，就将其加入串首，直到搜索完整个串为止。
代码：
bool get_largest_sub(const char *src,char* &largest_sub){if (src==NULL){return false;}else { int sLen=strlen(src); if (largest_sub==NULL||strlen(largest_sub)<sLen) { if (largest_sub==NULL) { largest_sub=(char *)malloc(sLen+1); }else { largest_sub=(char*)realloc(largest_sub,sLen+1); } }largest_sub[sLen-1]=src[sLen-1];int j=sLen-1;for (int i=sLen-2;i>=0;i--){if (src[i]>=largest_sub[j]){largest_sub[--j]=src[i];}}int p,q;for (p=0,q=j;p<sLen&&q<sLen;p++,q++){largest_sub[p]=largest_sub[q];}largest_sub[p]='\0';return true;}}