题目描述
一天可以被分为 n 个时段。
一个工人的每日工作安排可以用一个长度为 n 的 01 序列 a1,a2,…,an 来表示。
ai 为 0 表示第 i 个时间段是工作时间,ai 为 1 表示第 i 个时间段是休息时间。
工人日复一日的严格按照这个工作安排来进行工作和休息。
请问,工人的最长连续休息时间有多长(单位:时段)?
注意,连续休息时间可能跨天。
保证工人至少在一个时间段处于工作状态。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
每组数据输出一行结果,表示最长连续休息时间。
数据范围
1≤T≤10,
1≤n≤2×105,
0≤ai≤1,
同一测试点内所有 n 的和不超过 2×105。
样例
输入样例:
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
算法1
(滑动窗口) $O(n)$
1.拼接
2.滑动窗口
时间复杂度
参考文献
python3 代码
T = int(input())
for _ in range(T):
n = int(input())
nums = [int(x) for x in input().split()]
nums = nums + nums
l = 0
r = 0
res = 0
while r < 2 * n:
if nums[r] == 1:
r += 1
else:
res = max(res, r - l)
r += 1
l = r
if l < r:
res = max(res, r - l)
print(res)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int T; cin >> T;
while (T -- > 0)
{
int n; cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i ++)
cin >> nums[i];
for (int i = 0; i < n; i ++)
nums.push_back(nums[i]);
int res = 0;
int l = 0;
int r = 0;
while (r < 2 * n)
{
if (nums[r] == 1)
r ++;
else
{
res = max(res, r - l);
r ++;
l = r;
}
}
if (l < r)
res = max(res, r - l);
cout << res << endl;
}
return 0;
}
java 代码
import java.util.* ;
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while (T -- > 0)
{
int n = scan.nextInt();
int [] nums = new int [2 * n];
for (int i = 0; i < n; i ++)
nums[i] = scan.nextInt();
for (int i = n; i < 2*n ; i ++)
nums[i] = nums[i - n];
int res = 0;
int l = 0;
int r = 0;
while (r < 2 * n)
{
if (nums[r] == 1)
r ++;
else
{
res = Math.max(res, r - l);
r ++;
l = r;
}
}
if (l < r)
res = Math.max(res, r - l);
System.out.println(res);
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla