(C卷,100分)- 滑动窗口最大和（Java & JS & Python & C）

题目描述

有一个N个整数的数组，和一个长度为M的窗口，窗口从数组内的第一个数开始滑动直到窗口不能滑动为止，

每次窗口滑动产生一个窗口和（窗口内所有数的和），求窗口滑动产生的所有窗口和的最大值。

输入描述

• 第一行输入一个正整数N，表示整数个数。（0<N<100000）
• 第二行输入N个整数，整数的取值范围为[-100,100]。
• 第三行输入一个正整数M，M代表窗口的大小，M<=100000，且M<=N。

输出描述

• 窗口滑动产生所有窗口和的最大值。

用例

题目解析

此题应该是考察我们如何计算新的滑动窗口的值，一般有两种方式：

1、将滑动窗口中的元素值相加求和

2、基于前一个滑动窗口的和sum，计算新的滑动窗口的和，原理如下

如上图所示，第二个滑动窗口，相当于第一个滑动窗口减去10，加上15。

公式如下：i为第二个滑动窗口的起点索引，sum为第一个滑动窗口的和

sum = sum – arr[i – 1] + arr[i + m – 1];

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 3) {
    const n = lines[0] - 0;
    const arr = lines[1].split(" ").map(Number);
    const m = lines[2] - 0;

    console.log(getMaxWindowSum(arr, n, m));

    lines.length = 0;
  }
});

function getMaxWindowSum(arr, n, m) {
  let sum = arr.slice(0, m).reduce((p, c) => p + c);
  let ans = sum;

  for (let i = 1; i <= n - m; i++) {
    sum += arr[i + m - 1] - arr[i - 1];
    ans = Math.max(ans, sum);
  }

  return ans;
}

Java算法源码

import java.util.Scanner;

public class Main {
  // 输入获取
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }

    int m = sc.nextInt();

    System.out.println(getResult(n, arr, m));
  }

  // 算法入口
  public static int getResult(int n, int[] arr, int m) {
    int sum = 0;
    for (int i = 0; i < m; i++) { // 初始滑窗内部和
      sum += arr[i];
    }

    int ans = sum;

    for (int i = 1; i <= n - m; i++) {
      sum += arr[i + m - 1] - arr[i - 1]; // 基于初始滑窗进行差异求和，避免O(n)求和
      ans = Math.max(ans, sum);
    }

    return ans;
  }
}

Python算法源码

# 输入获取
n = int(input())
arr = list(map(int, input().split()))
m = int(input())


# 算法入口
def getResult():
    sumV = sum(arr[:m])
    ans = sumV

    for i in range(1, n-m+1):
        sumV += arr[i+m-1] - arr[i-1]
        ans = max(ans, sumV)

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

#define MAX(a,b) a > b ? a : b

int getResult(int n, int nums[], int m);

int main() {
    int n;
    scanf("%d", &n);

    int nums[n];
    int idx = 0;
    while(scanf("%d", &nums[idx++])) {
        if(getchar() != ' ') break;
    }

    int m;
    scanf("%d", &m);

    printf("%dn", getResult(n, nums, m));

    return 0;
}

int getResult(int n, int nums[], int m) {
    int sum = 0;
    for(int i=0; i<m; i++) {
        sum += nums[i];
    }

    int ans = sum;
    for(int i=1; i<=n-m; i++) {
        sum += nums[i+m-1] - nums[i-1];
        ans = MAX(ans, sum);
    }

    return ans;
}