題目：

輸入一段字符串（由字母構成），找出這段字符串中連續(xù)的最長的遞增字符。

舉例：
字符串：eahcu
結果：acu, ahu, ehu

思路：

本題有兩種思路求解，一種是遞歸的形式，首先找到最后一位字符，將其加入到結果集中，然后需要進行兩步查找：

一步是找大于結果集中第一位字符的字符，并將該字符加入到結果集中。

另一步是將小于結果集中第一位字符的字符加入到結果集中指定的字符串中，從而更新結果集。

還有一種方法是動態(tài)規(guī)劃的方法。
動態(tài)規(guī)劃最重要的就是找到狀態(tài)方程和狀態(tài)數(shù)組。狀態(tài)數(shù)組中每個數(shù)字代表的意義是從字符串首位到當前字符遞增序列的最長長度。之后是狀態(tài)方程，一旦發(fā)現(xiàn)當前字符大于之前的某個字符則更新當前字符的狀態(tài)值，更新為大于的字符的狀態(tài)值加上1。

在更新狀態(tài)值的過程中也需要更新子字符串。一旦當前字符大于之前的某個字符ch，則更新子字符，將所有狀態(tài)值小于當前字符狀態(tài)值的子字符串加上當前字符。最后取長度最大的子字符串。

代碼：

遞歸：

def longestConsective(str):
    if len(str) == 1:
        return {str}
    results = longestConsective(str[1:])
    solution = set(results)
    if all(chr[0] < str[0] for chr in results):
        solution.add(str[0])
    solution.update(str[0] + chr for chr in results if str[0] < chr[0])
    return solution

if __name__ == '__main__':
    str = input('Please input the string: ')
    results = longestConsective(str)
    max_len = max(len(str) for str in results)
    ares = sorted(result for result in results if len(result) == max_len)
    print(ares)

動態(tài)規(guī)劃：

def dplongestConsective(str):
    '''
    Find longest consecutive string by dynamic programming.
    :param str: 
    :return: 
    '''
    if not str:
        return ''
    solution = [(1, {str[i]}) for i in range(len(str))]
    max_length = 1
    for i in range(1, len(str)):
        length_so_far = 1
        for j in range(i):
            length, good_words = solution[j]
            if length < length_so_far - 1:
                continue
            if str[j] > str[i]:
                continue
            if length == length_so_far - 1:
                solution[i][1].update(w + str[i] for w in good_words)
            else:
                length_so_far = length + 1
                solution[i] = length_so_far, {w + str[i] for w in good_words}
            max_length = max(max_length, length_so_far)
    return sorted(w for (length, set_of_words) in solution if length == max_length
                  for w in set_of_words)