题目描述
给定一个长度为 n 的正整数数列 a1,a2,…,an。
初始时,数列中的每个元素要么处于可选状态,要么处于不可选状态。
你可以选择一个长度恰好为 k 的区间 [i,i+k−1],使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。
请问,在经过此操作后,所有处于可选状态的元素之和最大是多少。
输出格式
一行一个整数,表示答案。
数据范围
对于 30% 的数据,1≤k≤n≤1000
对于 100% 的数据,1≤k≤n≤105,1≤ai≤105
样例
输入样例:
3 1
2 5 4
0 0 1
输出样例:
9
滑动窗口
令数值数组为 a,可选数组为 b。
在接收【可选数组】列表 b 时,做以下两个操作:
- 累计所有本身已经是【可选】的值。
- 将所有本身已经是【可选】的值变为 0。
问题转换成【如何在一个数组中取得“长度固定”的窗口的最大值是多少】。
然后使用【滑动窗口】求解即可。
时间复杂度:$O(n)$
空间复杂度:$O(1)$
import java.util.*;
class Main {
static int[] a = new int[100009];
static int[] b = new int[100009];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
long ans = 0;
for (int i = 1; i <= n; i++) {
b[i] = sc.nextInt();
if (b[i] == 1) {
ans += a[i];
a[i] = 0;
}
}
long max = 0;
long sum = 0;
for (int i = 1; i <= n; i++) {
if (i <= k) {
sum += a[i];
} else {
int del = a[i - k], add = a[i];
sum = sum - del + add;
}
max = Math.max(max, sum);
}
System.out.println(ans + max);
}
}