題目描述

輸入長度為 $n$ 的一個正整數序列，要求輸出序列中最長連號的長度。

連號指在序列中，從小到大的連續自然數。

輸入格式

第一行，一個整數 $n$。

第二行，$n$ 個整數 $a_i$，之間用空格隔開。

輸出格式

一個數，最長連號的個數。

輸入輸出樣例

輸入

10
1 5 6 2 3 4 5 6 8 9

輸出

5

說明/提示

數據規模與約定

對于 $100\%$ 的數據，保證 $1\le n\le 10^4$，$1\le a_i\le 10^9$。

方式-遍歷

代碼

class Solution:@staticmethoddef oi_input():"""從標準輸入讀取數據"""num, nums = int(input()), list(map(int, input().split()))return num, nums@staticmethoddef oi_test():"""提供測試數據"""return 10, [1, 5, 6, 2, 3, 4, 5, 6, 8, 9]@staticmethoddef solution(num, nums):'''遍歷'''max_len, current = 1, 1  # 最大 與 當前for i in range(1, num):if nums[i] == nums[i - 1] + 1:current += 1max_len = max(max_len, current)else:current = 1print(max_len)oi_input = Solution.oi_input
oi_test = Solution.oi_test
solution = Solution.solutionif __name__ == '__main__':num, nums = oi_test()# num, nums = oi_input()solution(num, nums)

流程圖

方式-雙指針-滑動窗口

代碼

class Solution:@staticmethoddef oi_input():"""從標準輸入讀取數據"""num, nums = int(input()), list(map(int, input().split()))return num, nums@staticmethoddef oi_test():"""提供測試數據"""return 10, [1, 5, 6, 2, 3, 4, 5, 6, 8, 9]@staticmethoddef solution(num, nums):max_len, left = 1, 0for right in range(num - 1):  # right 表示當前檢查的位置的前一個if nums[right + 1] != nums[right] + 1:left = right + 1# 窗口范圍為 [left, right+1]# 前面加1 是因為 right 跟 right + 1 比的，括號外面加1 是因為要包含被減去的位置current_len = (right + 1 - left) + 1max_len = max(max_len, current_len)print(max_len)oi_input = Solution.oi_input
oi_test = Solution.oi_test
solution = Solution.solutionif __name__ == '__main__':num, nums = oi_test()# num, nums = oi_input()solution(num, nums)

流程圖

方式-遞歸-緩存

代碼

class Solution:@staticmethoddef oi_input():"""從標準輸入讀取數據"""num, nums = int(input()), list(map(int, input().split()))return num, nums@staticmethoddef oi_test():"""提供測試數據"""return 10, [1, 5, 6, 2, 3, 4, 5, 6, 8, 9]@staticmethoddef solution(num, nums):import sysfrom functools import lru_cachesys.setrecursionlimit(1000000)  # 強行增大遞歸深度@lru_cache(maxsize=None)def max_consecutive_length_from_index(i):if i == 0:return 1if nums[i] == nums[i - 1] + 1:return max_consecutive_length_from_index(i - 1) + 1else:return 1print(max(max_consecutive_length_from_index(i) for i in range(num)))oi_input = Solution.oi_input
oi_test = Solution.oi_test
solution = Solution.solutionif __name__ == '__main__':num, nums = oi_test()# num, nums = oi_input()solution(num, nums)

流程圖