题目描述
一天可以被分为 $n$ 个时段。
一个工人的每日工作安排可以用一个长度为 $n$ 的 01 序列 $a_1$,$a_2$,…,$a_n$ 来表示。
$a_i$ 为 0 表示第 $i$ 个时间段是工作时间,$a_i$ 为 1 表示第 $i$ 个时间段是休息时间。
工人日复一日的严格按照这个工作安排来进行工作和休息。
请问,工人的最长连续休息时间有多长(单位:时段)?
注意,连续休息时间可能跨天。
保证工人至少在一个时间段处于工作状态。
样例
输入样例:
4
5
1 0 1 0 1
6
0 1 0 1 1 0
7
1 0 1 1 1 0 1
3
0 0 0
输出样例:
2
2
3
0
算法
(简单枚举) $O(n)$
直观来讲,我们只需要简单地扫一遍各个数就可以了。
我们可以引入$cnt$,来记录连续1的个数。然后每次更新到$res$中。但是由于可以尾部和首部连休,因此我们可以再引入一个变量$prev$,表示从0开始,最大连续1的个数,当扫到下标为$n-1$的时候,再将$cnt+prev$更新到$res$中即可。
最后得到的$res$进行输出即可。
时间复杂度
由于整体扫描了一遍序列,所以时间复杂度是$O(n)$级别的。
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2e5+10;
int a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof a);
int n;
scanf("%d",&n);
for(int i = 0;i<n;i++)scanf("%d",&a[i]);
int ans = 0,cnt = 0,prev = 0;
bool flag = true;//定义标记flag,如果flag为true说明当前正在统计从头开始的连续1的个数,便更新prev;若为false,则不更新prev。
for(int i = 0;i<n;i++)
{
if(a[i]&&i==0)
{
prev++;
cnt++;
}
else if(a[i]==0)
{
cnt=0;
flag=false;
}
else if(a[i])
{
cnt++;
if(flag)prev++;
}
ans = max(ans,cnt);
}
ans = max(ans,prev+cnt);
printf("%d\n",ans);
}
return 0;
}