题解 | #最大子序列#
最大子序列
https://www.nowcoder.com/practice/17ba5b5df1fc49ca8d6cf8ea407b1972
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)
（第一个题解，看答得人不多就写了）
投递小米集团等公司10个岗位