暴力枚举 $O(n^2)$
遇到1固定再次向后遍历,注意一定要更新i, 不然就T了
破环成链参考:
破环成链的小技巧
来源:
USACO training 1.2 断开的项链
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N = 200010;
int a[N * 2];
int t, n;
int main( ) {
scanf("%d", &t);
while( t -- ) {
scanf("%d", &n);
int cnt = 0;
// n变为2n,破环成链
for( int i = 0; i < n; i++ ) {
scanf("%d", &a[i]);
a[i+n] = a[i];
}
int res = 0;
for ( int i = 0; i < 2 * n; i++ ) {
int tmp = 0;
if( a[i] == 1 ) {
int j = i;
while( a[j] == 1 ) {
j++;
tmp++;
}
i += tmp; // 这里要更新,不然会TLE
}
res = max(res, tmp);
if( i > n && a[i] == 0 ) break;
}
cout << res << endl;
}
return 0;
}