3493. 最大的和

问题重述：

给定一个长度为 n的正整数数列 a1,a2,…,an。

初始时，数列中的每个元素要么处于可选状态，要么处于不可选状态。

你可以选择一个长度恰好为 k 的区间 [i,i+k−1]，使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。

请问，在经过此操作后，所有处于可选状态的元素之和最大是多少。

输入格式

第一行包含两个整数 n和 k。

第二行包含 n个整数 ai。

第三行包含一个长度为 n 的 01 序列，如果第 i个数为 1，表示 ai 的初始状态为可选，如果第 i 个数为 0，表示 ai的初始状态为不可选。

输出格式

一行一个整数，表示答案。

数据范围

对于 30%30% 的数据，1≤k≤n≤1000
对于 100%100% 的数据，1≤k≤n≤10^{5,1≤ai≤10}5

输入样例1：

3 1
2 5 4
0 0 1

输出样例1：

9

输入样例2：

4 3
10 5 4 7
0 1 1 0

输出样例2：

19

问题分析：

本题给定了两个数组，一个为数值，一个为对应数值是否可选，要求在某一区间内数组数组全部变为可选后，求数值数组中所有的可选数值的和，求出可选值的最大值。我们可以先开始的时候先算出数值数组中的可选数值总和maxSum（初始时他最大），然后将每一个区间内所有不可选的数值（也就是选择数组中为0）加入maxSum记为sum，将sum与maxSum进行对比，若sum>maxSum，则将最大和数值更新为sum。将整个数值数组遍历完成后，此时的maxSum就是最大和。

解法：

双指针、前缀和

解题：

双指针解法代码：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入n和k
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        long sum = 0;
        long maxSum = 0;
        int []numberArrays = new int[n];
        int []selected = new int[n];
        // 初始化数据ai,求数据总和
        for (int i = 0; i < n; i++) {
            numberArrays[i] = scanner.nextInt();
            maxSum += numberArrays[i];
        }
        // 初始化数据是否可选，同时把一开始的最大值计算出来
        for (int i = 0; i < n; i++) {
            selected[i] = scanner.nextInt();
            if (selected[i]==1){
                sum +=numberArrays[i];
            }
        }
        //当k=n时，最大和即为数据总和
        if (n != k ){
            maxSum = sum;    
            // 先将前k个数据设为可选
            for (int i = 0; i < k; i++) {
                if (selected[i] == 0){
                    sum += numberArrays[i];
                }
            }
            maxSum = sum;
            // 开始双指针
            for (int i = 0; i < n-k; i++) {
                if (selected[i] == 0){
                    sum = sum - numberArrays[i];
                }
                if (selected[i+k] == 0){
                    sum = sum +numberArrays[i+k];
                }
                if (sum > maxSum){
                    maxSum = sum;
                }
            }
        }
        System.out.println(maxSum);

    }
}

解析：

​ 输入n、k，for循环输入初始化数据ai，因为当n=k时，最大和即为所有数值数组的总和，所以循环时将输入的所有的数值先全部相加（maxSum）。第二个循环输入01给定数值数组中的数值是否可选，因为最大和一定包括这些初始可选数值的和，所以在输入时将所有可选的先求和（sum）。初始化完成后开始求解，当n=k时，直接输出maxSum，当n不等于k时，首先将maxSum设置为sum，计算长度为k的数组中不可选择的数据求和加到sum中，与maxSum进行对比，若sum大于maxSum，将maxSum数值置为sum。区间依次向右移动，减掉最左边的值，加上最右边的值，求得的sum依次与maxSum进行对比，遍历完成后，maxSum即为最大值。直接输出maxSum。

双指针总结：

​ 双指针一般有快慢指针、对撞指针、以及滑动窗口，本题使用的就是滑动窗口

快慢指针：快慢指针同时向一个方向移动，快指针较快（可以是移动速度，也可以是初始位置较后），慢指针较慢，经过一定时间以后两者将会相遇或者快指针到达边界。常用于校验链表中是否有环。

对撞指针：两个指针一左一右同时向中间以相同的速度移动。经过一定时间两者将会相遇。

滑动窗口：左右两个指针，指针之间看作一个窗口，两指针从起点开始，右端指针向右依次扩张，直到达到要求，停止，左端指针依次向右扩张，直到不符合要求，此时停止左端指针，对最优解结果进行更新，继续开始移动右端指针，循环该操作。（本题窗口大小固定使用滑动窗口，只要一直往右遍历得出最优解就可以）

前缀和：

​ 前缀和一般用于求有关区间的问题，创建一个数组，其中每一个数据都是第1个到当前区间的数据，当我们需要使用某个区间内的数据时，直接使用该前缀和数组，就不需要再进行依次计算了。（一维前缀和是区间，二维前缀和为面积）