解题思路

• 从题目可知，我们需要循环选择开始的位置，也就是说循环给出的每一项作为第一步
• 第一步选择好之后，需要循环第一步后面的位置，找到比第一步大的位置，继续走
  • 这里需要分情况：
    • 遇到比第一步大的，就选择其作为走第二步的位置
    • 忽略这个位置，继续往后选择第二步需要走的位置
  • 从这里，可以看到我们是需要循环完第一步后面的全部位置的，不能遇到比第一步大的就结束循环
• 选择好第二步之后，需要找到第三步的位置（是不是很熟悉？）。很明显，选择第三步的方法和选择第二步的方法没有任何区别，因此使用递归是很好的方案。

初步代码

• 在迭代中，找出后面数字中，比当前位置的数字大的，然后循环，并记录下进入循环的数字，就可以得出全部的行走方案。
• 在全部的迭代方案中，选择步骤最大的即可。

res = []

def func(a, s):
    if len(s) == 1:
        if s[0] > a:
            return [[s[0]]]
        else:
            return []

    all_steps = []
    for i in range(len(s)):
        steps = []
        if s[i] > a:
            new_steps = func(s[i], s[i+1:])
            if new_steps:
                for step in func(s[i], s[i+1:]):
                    steps.append([s[i]] + step)
            else:
                steps.append([s[i]])
        all_steps.extend(steps)
    return all_steps


input()
s = list(map(int, input().split()))
all_steps = func(0, s)
print(max(map(len, all_steps)))

测试自测用例可以通过，但是提交时发现耗时太久了。

优化代码

• 本次修改不在记录每次走过的位置，以减少列表添加和循环的时间开销
• 不过这个方案对于调试不太友好，不能快速定位错误的原因

res = []

def func(a, s):
    if len(s) == 1:
        if s[0] > a:
            return 1
        else:
            return 0

    all_steps = 0
    for i in range(len(s)):
        steps = 0
        if s[i] > a:
            steps = max(steps, func(s[i], s[i+1:]) + 1)
        all_steps = max(steps, all_steps)
    return all_steps


input()
s = list(map(int, input().split()))
all_steps = func(0, s)
print(all_steps)

提交之后发现，时间还是超限

最终方案

• 现在存在 2 中情况：
  • 第一步选择 index 为 0 的数字，第二步选择 index 为 3 的数字
  • 第一步选择 index 为 3 的数字
• 这 2 中情况下，返回的结果应该是一样的，但按照上面的代码，我们需要重复计算，当数字很大时时间开销非常大。我们只需要将每次计算过的结果存储下，那么就能减少重复计算的时间开销

res = {}

def func(a, s):
    if len(s) == 1:
        if s[0] > a:
            return 1
        else:
            return 0

    ss = "".join(map(str, s))
    if ss in res:
        return res[ss]

    all_steps = 0
    for i in range(len(s)):      
        steps = 0
        if s[i] > a:
            steps = max(steps, func(s[i], s[i+1:]) + 1)
        all_steps = max(steps, all_steps)
    
    if ss not in res:
        res[ss] = all_steps
    return all_steps


input()
s = list(map(int, input().split()))
all_steps = func(0, s)
print(all_steps)