洛谷题单3-P1420 最长连号-python-流程图重构

题目描述

输入长度为 $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:
    @staticmethod
    def oi_input():
        """从标准输入读取数据"""
        num, nums = int(input()), list(map(int, input().split()))
        return num, nums

    @staticmethod
    def oi_test():
        """提供测试数据"""
        return 10, [1, 5, 6, 2, 3, 4, 5, 6, 8, 9]

    @staticmethod
    def solution(num, nums):
        '''遍历'''
        max_len, current = 1, 1  # 最大 与 当前

        for i in range(1, num):
            if nums[i] == nums[i - 1] + 1:
                current += 1
                max_len = max(max_len, current)
            else:
                current = 1
        print(max_len)


oi_input = Solution.oi_input
oi_test = Solution.oi_test
solution = Solution.solution

if __name__ == '__main__':
    num, nums = oi_test()
    # num, nums = oi_input()
    solution(num, nums)

流程图

方式-双指针-滑动窗口

代码

class Solution:
    @staticmethod
    def oi_input():
        """从标准输入读取数据"""
        num, nums = int(input()), list(map(int, input().split()))
        return num, nums

    @staticmethod
    def oi_test():
        """提供测试数据"""
        return 10, [1, 5, 6, 2, 3, 4, 5, 6, 8, 9]

    @staticmethod
    def solution(num, nums):
        max_len, left = 1, 0

        for 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) + 1
            max_len = max(max_len, current_len)
        print(max_len)


oi_input = Solution.oi_input
oi_test = Solution.oi_test
solution = Solution.solution

if __name__ == '__main__':
    num, nums = oi_test()
    # num, nums = oi_input()
    solution(num, nums)

流程图

方式-递归-缓存

代码

class Solution:
    @staticmethod
    def oi_input():
        """从标准输入读取数据"""
        num, nums = int(input()), list(map(int, input().split()))
        return num, nums

    @staticmethod
    def oi_test():
        """提供测试数据"""
        return 10, [1, 5, 6, 2, 3, 4, 5, 6, 8, 9]

    @staticmethod
    def solution(num, nums):
        import sys
        from functools import lru_cache

        sys.setrecursionlimit(1000000)  # 强行增大递归深度

        @lru_cache(maxsize=None)
        def max_consecutive_length_from_index(i):
            if i == 0:
                return 1
            if nums[i] == nums[i - 1] + 1:
                return max_consecutive_length_from_index(i - 1) + 1
            else:
                return 1

        print(max(max_consecutive_length_from_index(i) for i in range(num)))


oi_input = Solution.oi_input
oi_test = Solution.oi_test
solution = Solution.solution

if __name__ == '__main__':
    num, nums = oi_test()
    # num, nums = oi_input()
    solution(num, nums)

流程图