AcWing 3493. 最大的和(java : slide window)
原题链接
简单
作者:
runminh
,
2021-05-12 01:23:57
,
所有人可见
,
阅读 377
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
boolean[] b = new boolean[n];
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = sc.nextInt();
for (int i = 0; i < n; i++)
if (sc.nextInt() == 1)
b[i] = true;
else b[i] = false;
maxSum(n, k, a, b);
return;
}
static void maxSum(int n,
int k,
int[] a,
boolean[] b) {
if (a == null || b == null) return ;
long sum = 0;
long max = 0;
// firstly, figure out all eles in the arr a which are avaiable(stat 1 in b)
for (int i = 0; i < n; i++)
if (b[i]) sum += a[i];
long s = 0; // range sum
// then using slide window to add all unavaiable eles in range
// m ~ m + k, add all those eles and compare & keep the max.
for (int i = 0; i < n; i++) {
if (!b[i]) s += a[i];
if (i >= k && !b[i - k]) s -= a[i - k]; // >= k
max = Math.max(s, max);
}
System.out.println(max + sum);
}
}