动态规划 P1420 最长连号 python题解

动态规划 P1420 最长连号 python题解

题目描述

输入长度为 n 的一个正整数序列，要求输出序列中最长连号的长度。

连号指在序列中，从小到大的连续自然数。

输入格式

第一行，一个整数 n。

第二行，n 个整数 ai​，之间用空格隔开。

输出格式

一个数，最长连号的个数。

代码：

# 核心方程 dp[i]=dp[i-1]+1
# 意思是当前这个数的值等于它的上一个数的值加一
n = int(input())  # 输入整数n
dp_ = list(map(int, input().split()))  # 输入一连串整数an，用空格分隔，输出dp结果为[1,5,6,2,3,4,5,6,8,9]
max_ = 0  # 用来记录最大连数
cur = 1  # 用来记录临时最大连数,默认为1，即连数只有它本身时
for i in range(1, n):  # 从第二个开始遍历，一直到n个if dp_[i] == dp_[i - 1] + 1:cur += 1else:if cur > max_:max_ = curcur = 1  # 重新开始计算临时连数
if cur > max_:  # 用来判断特殊情况：即当最后一个也是最大连数中的一个时，因为还cur没赋值给max_，所以需要判断一下cur是否大于max_print(cur)
else:print(max_)