如何求解字符串中字典序最大的子序列：快速解析

【出自MGYD笔试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

给定一个字符串，求串中字典序最大的子序列。字典序最大的子序列是这样构造的：给定字符串a0a1…an-1，首先在字符串a0a1…an-1中找到值最大的字符ai，其次在剩余的字符串ai+1…an-1中找到值最大的字符aj，然后在剩余的aj+1…an-1中找到值最大的字符ak…直到字符串的长度为0，则aiajak…即为答案。

分析与解答：

方法一：顺序遍历法

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

以"acbdxmng"为例，首先对字符串遍历一遍，找出最大的字符‘x’；接着从‘m’开始遍历，找出最大的字符‘n’；然后从‘g’开始遍历，找到最大的字符‘g’。因此“acbdxmng”的最大子序列为“xng”。实现代码如下：

程序的运行结果如下：(www.xing528.com)

xng

算法性能分析：

这种方法在最坏情况下（字符串中的字符按降序排列）的时间复杂度为O（n^2）；在最好情况下（字符串中的字符按升序排列）的时间复杂度为O（n）。此外这种方法需要申请n+1个额外的存储空间，因此，空间复杂度为O（n）。

方法一：逆序遍历法

通过对上述运行结果进行分析，发现an-1^一定在所求的子串中，接着逆序遍历字符串，大于或等于an-1的字符也一定在子串中，依次类推，一直往前遍历，只要遍历到的字符大于或等于子串首字符，就把这个字符加到子串首。由于这种方法首先找到的是子串的最后一个字符，最后找到的是子串的第一个字符，因此，在实现的时候首先按照找到字符的顺序把找到的字符保存到数组中，最后再对字符数组进行逆序，从而得到要求的字符。以"acbdxmng"为例，首先，字符串的最后一个字符‘g’一定在子串中，接着逆向遍历找到大于或等于‘g’的字符‘n’加入到子串中“gn”（子串的首字符为‘n’），接着继续逆向遍历找到大于或等于‘n’的字符‘x’加入到子串中“gnx”，接着继续遍历，没有找到比‘x’大的字符。最后对子串“gnx”逆序得到“xng”。实现代码如下：

算法性能分析：

这种方法只需要对字符串遍历一次，因此，时间复杂度为O（n）。此外，这种方法需要申请n+1个额外的存储空间，因此空间复杂度为O（n）。