【正确答案】方法一：顺序遍历法最直观的思路就是首先遍历一次字符串，找出最大的字符a_i，接着从a_i开始遍历再找出最大的字符，依此类推直到字符串长度为0。
   以“acbdxmng”为例，首先对字符串遍历一遍找出最大的字符‘x’，接着从‘m’开始遍历找出最大的字符‘n’，然后从‘g’开始遍历找到最大的字符为‘g’，因此“acbdxmng”的最大子序列为“xng”。实现代码如下：
   #方法功能: 求串中字典序最大的子序列
   def getLargestSub(src):
   if src==None:
   return None
   lens=len(src)
   largestSub=[None]*(lens+1)
   k=0
   i=0
   while i＜lens:
   largestSub[k]=list(src)[i]
   j=i+1
   while j＜lens:
   #找出第i个字符后面最大的字符放到largestSub[k]中
   if list(src)[j]＞largestSub[k]:
   largestSub[k]=list(src)[j]
   i=j
   j+=1
   k+=1
   i+=1
   return ".join(largestSub[0:k])
   
   if __name__=="__main__":
   s="acbdxmng"
   result=getLargestSub(s)
   if result==None:
   print "字符串为空"
   else:
   print result
   程序的运行结果为：
   xng
   算法性能分析：
   这种方法在最坏的情况下(字符串中的字符按降序排列)时间复杂度为O(n²)；在最好的情况下(字符串中的字符按升序排列)时间复杂度为O(n)。此外这种方法需要申请n+1个额外的存储空间，因此，空间复杂度为O(n)。
   方法一：逆序遍历法
   通过对上述运行结果进行分析，发现a_n-1一定在所求的子串中，接着逆序遍历字符串，大于或等于a_n-1的字符也一定在子串中，依次类推，一直往前遍历，只要遍历到的字符大于或等于子串首字符，就把这个字符加到子串首。由于这种方法首先找到的是子串的最后一个字符，最后找到的是子串的第一个字符，因此，在实现的时候首先按照找到字符的顺序把找到的字符保存到数组中，最后再对字符数组进行逆序，从而得到要求的字符。以”acbdxmng”为例，首先，字符串的最后一个字符‘g’一定在子串中，接着逆向遍历找到大于或等于‘g’的字符‘n’加入到子串中“gn”(子串的首字符为‘n’)，接着继续逆向遍历找到大于或等于‘n’的字符‘x’加入到子串中“gnx”，接着继续遍历，没有找到比‘x’大的字符。最后对子串“gnX”逆序得到“xng”。实现代码如下：
   def getLargestSub(src):
   if src==None:
   return None
   lens=len(src)
   largestSub=[None]*(lens+1)
   #最后一个字符一定在子串中
   largestSub[0]=list(src)[lens-1]
   i=lens-2
   j=0
   #逆序遍历字符串
   while i＞0:
   if ord(list(src)[i])＞=ord(largestSub[j]):
   j+=1
   largestSub[j]=list(src)[i]
   i-=1
   #largestSub[j+1]="
   largestSub-largestSub[0:j+1]
   #对子串进行逆序
   i=0
   while i＜j:
   tmp=largestSub[i]
   largestSub[i]=largestSub[j]
   largestSub[j]=tmp
   i+=1
   j-=1
   return ".join(largestSub)
   
   if __name__=="__mam__":
   s="acbdxmng"
   result=getLargestSub(s)
   if result==None:
   print "字符串为空"
   else:
   print result
   算法性能分析：
   这种方法只需要对字符串遍历一次，因此，时间复杂度为O(n)。此外，这种方法需要申请n+1个额外的存储空间，因此空间复杂度为O(n)。

【答案解析】[考点] 如何求解字符串中字典序最大的子序列