二 562. 壁画 (前缀和)

562. 壁画 (前缀和)

思路：壁画最终应是长度为mid=(N+1)/2的连续一段，而被摧毁的墙则在两边，故以终点为标志从mid遍历到N，确定最大的一段美观总分，同时因为多次计算一段美观评分耗时多，可提前计算出美观评分的前缀和，然后对应的美观总分=sum[i]-sum[i - mid]。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int n;
        String line = "";
        char[] walls;
        int[] sum;
        for (int cases = 1; cases <= T; cases++) {
            n = sc.nextInt();
            sum = new int[n + 2];
            sc.nextLine();
            line = sc.nextLine();
            for (int i = 1; i <= n; i++) {
                sum[i] = sum[i - 1] + line.charAt(i - 1) - '0';
            }
            int res = 0, mid = n + 1 >> 1;
            for (int i = mid; i <= n; i++) {
                res = Math.max(res, sum[i] - sum[i - mid]);
            }
            System.out.println("Case #" + cases + ": " + res);
        }
    }
}