题解 | #最大子序列#

s = input().strip()
# 动态规划：dp[i]以i结尾的最大字典序
'''
t e/te s/ts/tes t/tt/tes/test
'''
dp = ["" for _ in range(len(s))]
dp[0] = s[0]
for i in range(len(s)):
    for j in range(0, i):
        dp[i] = max(dp[j]+s[i], dp[i], s[i])
print(dp[len(s)-1])

动态规划可以解决大多数的子序问题，

输入test，每一轮比较如注释：

t e/te s/ts/tes t/tt/tes/test

dp的更新考虑每一个前序dp加上当前字符的最大值；或者重启起始字符串，从s[i]开始

时间复杂度O(n2)

（第一个题解，看答得人不多就写了）