算法1

(经典 前缀和) $O(n)$

需要： 字符串当中得分最高的已知长度的连续子串
- 前缀和求解每个长度为k的子串(l,r)的得分，求最大值MAX

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5000010;
int n;
int s[N];
char nums[N];
int main()
{
    //性质 [n/2]上取整 = k = （n + 1）/2 下取整
    // 长度为k的任意一段
    int T;
    scanf("%d", &T); //数比较大 scanf好些
    for (int C = 1; C <= T; C++)
    {
        scanf("%d%s", &n, nums + 1); //下标从1开始
        for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + nums[i] - '0'; //前缀和 O(1)来解决连续区间子集最大值
        int k = (n + 1) / 2;
        int res = 0;
        for (int i = k; i <= n; i++)
            res = max(res, s[i] - s[i - k]); //遍历一遍 长度为k的所有子段
        printf("Case #%d: %d\n", C, res);
    }

    return 0;
}