首页 > 试题广场 >

最长区间

[编程题]最长区间

热度指数：4514 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

拉齐有一个 01 序列，他可以对这个序列进行任意多次变换，每次变换都是把序列的最后若干个元素放到最前面，例如：010011，将最后 3 个元素 011 放到最前面，序列变为 011010 。所有变换结束后，拉齐需要挑出一个全为 1 的连续区间，要求最大化区间长度。

数据范围：输入序列长度满足 $1 \le n \le 50000 \$

输入描述:

共一行，一个01串，仅包含0或1。序列长度不超过50000。

输出描述:

一个整数，表示最长区间的长度。

示例1

输入

输出

说明

把最后两个 1 放到最前面，形成一个长度为 4 的全 1 区间

算法知识视频讲解

你吃菜吗

发表于 2023-02-18 01:26:18

思路：最重要的是理解序列变换的本质是：把序列看作一个首尾相连的环，不管怎样变换，序列里元素的相对位置都没有变。那么我们的任务就很清晰了，就是在一个元素固定的环内找到元素全为1的最长连续序列。处理：一个比较简单的处理方法就是把序列看作环之后，再处理为一个以0开头（或者没有0）的序列，然后从头进行展开全文