题目描述

一维前缀和

样例

import java.util.*;
/*
   先分析：每段已涂画必定相连  并且每涂一段画必有一段相邻的画被毁  所以涂画的区间就是总长度/2（并向上取整)，因为先涂再毁。

   算前缀和数组，去枚举所有区间就是总长度/2（并向上取整)的得分，找出最大的
*/
public class Main {
    static final int N = 5000010;
    static int[] a = new int[N+5];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int j = 1; j <= T; j ++) {
            int n = sc.nextInt();
            //向上取整
            int m = n + 1 >> 1;
            String s = sc.next();
            //s[i] = s[i - 1] + str.charAt(i - 1) - '0';
            for (int i = 1; i <= n; i ++) a[i] = a[i - 1] + Integer.parseInt(s.charAt(i - 1)+"");
            int res = 0;
            //寻找所有区间长度为m的前缀和 注意这里是a[i] - a[i - m]  
            //注意这里是a[i] - a[i - m]  模板是区间[l,r]对应a[r] - a[l - 1]也就是a[r] - a[r-(r-l+1)]也就是a[r] - a[r-m]
            for (int i = m; i <= n; i ++) res = Math.max(res, a[i] - a[i - m]);
            System.out.println("Case #" + j + ": " + res);
        }
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla