document.write('

方法一：顺序遍历法最直观的思路就是首先遍历一次字符串，找出最大的字符ai，接着从ai开始遍历再找出最大的字符，依此类推直到字符串长度为

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(n2

)；在最好的情况下(字符串中的字符按升序排列)时间复杂度为O(n)。此外这

种方法需要申请n+1个额外的存储空间，因此，空间复杂度为O(n)。

方法一：逆序遍历法

通过对上述运行结果进行分析，发现an-1一定在所求的子串中，接着逆序遍历字符串，大于或等于an-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__":