作者 ： Xia Xinyu
日期 : -08-20
原题链接
题目：一天可以被分为 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(双指针算法): 先统计出数组中值全为1的最长连续子序列长度，由于连续休息时间可能跨天，所以判断一天中的开始和结束时间段是否存在满足条件的子序列并求出长度之和(可能为一个或两个或不存在)，将两个长度取一个max即可。
代码1:
public class Main{public static void main(String[] args){Scanner in = new Scanner(System.in);int T = in.nextInt();while(T-- != 0){int n = in.nextInt();var a = new int[n];int cost = 0;for(int i = 0;i < n;i++) a[i] = in.nextInt();for(int i = 0;i < n;i++){if(a[i] == 0) continue;int j = i + 1;while(j < n && a[j] == 1) j++;cost = Math.max(cost,j - i);i = j;}int t = 0;for(int i = 0;i < n;i++) {if(a[i] == 1) t++;elsebreak;}for(int i = n - 1;i >= 0;i--) {if(a[i] == 1) t++;elsebreak;}cost = Math.max(t,cost);System.out.println(cost);}}}
时间复杂度：O(n )
空间复杂度：O(n)
思路2(双指针算法):将序列的头和尾连接起来，直接将序列复制一遍即可，然后利用双指针算法求出最长连续子序列，
代码2(相比第一种思路代码更加简洁):
import java.util.*;public class Main{public static void main(String[] args){Scanner in = new Scanner(System.in);int T = in.nextInt();while(T-- != 0){int n = in.nextInt();var a = new int[2 * n];int cost = 0;for(int i = 0;i < n;i++) a[i] = in.nextInt();for(int i = n;i < 2 * n;i++) a[i] = a[i - n];for(int i = 0;i < 2 * n;i++){if(a[i] != 1) continue;int j = i + 1;while(j < 2 * n && a[j] == 1) j++;cost = Math.max(cost,j - i);i = j;}System.out.println(cost);}}}
