DFS栈实现超时

时间复杂度O(n^2), 空间复杂度O(n) 到第17个测试用例时报超时。

n = int(input()) # 1 <= n <= 200
h = list(map(int, input().strip().split(' '))) # 1 <= val <= 350
maxl = 0
for i in range(n):
    walked = []
    if n - i < maxl:
        break
    walked.append(i)
    j = i + 1
    while walked:
        if j < n and h[j] > h[walked[-1]]:
            walked.append(j)
        elif j == n:
            maxl = len(walked) if len(walked) > maxl else maxl
            j = walked.pop()
        j += 1
print(maxl)

改用动态规划

时间复杂度O(n^2), 空间复杂度O(n)。

n = int(input())
h = list(map(int, input().strip().split(' ')))

# 创建以h[i]结尾的最长递增子序列的长度
dp = [1] * n

for i in range(n):
    for j in range(i):
        if h[i] > h[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))