文章目录
- 一、题目
- 🎃题目描述
- 🎃输入输出
- 🎃样例1
- 二、代码与思路参考
- 🎈C++语言思路
- 🎉C++代码
- 🎈Java语言思路
- 🎉Java代码
- 🎈Python语言思路
- 🎉Python代码
- 作者：KJ.JK
🍂个人博客首页： KJ.JK
🍂专栏介绍： 定期更新华为OD各个时间阶段的机试真题，每日定时更新，本专栏每篇的文章都会将使用C++、Python、Java三种语言进行更新解答，每个题目的思路分析都非常详细，超过百字欢迎大家订阅学习，代码可以直接运行使用
一、题目
🎃题目描述
有一个N个整数的数组，和一个长度为M的窗口，窗口从数组内的第一个数开始滑动直到窗口不能滑动为止，
每次窗口滑动产生一个窗口和（窗口内所有数的和），求窗口滑动产生的所有窗口和的最大值
🎃输入输出
输入
第一行输入一个正整数N，表示整数个数。（0<N<100000）
第二行输入N个整数，整数的取值范围为[-100,100]。
第三行输入一个正整数M，M代表窗口的大小，M<=100000，且M<=N。
输出
窗口滑动产生所有窗口和的最大值
🎃样例1
输入
6
12 10 20 30 15 23
3
输出
68
说明
窗口长度为3，窗口滑动产生的窗口和分别为10+20+30=60，20+30+15=65，30+15+23=68，15+23+12=50，
所以窗口滑动产生的所有窗口和的最大值为68
二、代码与思路参考
🎈C++语言思路
1、读取输入的整数N，表示数组的长度
2、读取输入的整数数组元素，将其存储在一个名为arr的向量中
3、读取输入的整数M，表示滑动窗口的长度
4、初始化变量window_sum为前M个元素的和，即窗口的初始和
5、初始化变量max_sum为window_sum，表示当前的最大和
6、从M开始，通过遍历数组来移动滑动窗口
- 在每个位置i，通过将窗口最左边的元素移出窗口并将窗口最右边的元素移入窗口，更新window_sum的值
- 检查window_sum是否大于max_sum，如果是，则将max_sum更新为window_sum
7、遍历完成后，max_sum将包含滑动窗口的最大和
8、输出max_sum作为结果
🎉C++代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N; // 输入N
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i]; // 输入数组元素
}
int M;
cin >> M; // 输入M
int window_sum = 0;
for (int i = 0; i < M; i++) {
window_sum += arr[i]; // 计算初始窗口和
}
int max_sum = window_sum; // 初始化最大和为初始窗口和
for (int i = M; i < N; i++) {
window_sum = window_sum - arr[i - M] + arr[i]; // 更新窗口和，减去窗口最左边的元素，加上窗口最右边的元素
max_sum = max(max_sum, window_sum); // 更新最大和
}
cout << max_sum << endl; // 输出最大和
return 0;
}
🎈Java语言思路
1、首先，从输入中获取数组的长度 N，并创建一个大小为 N 的整数数组 arr
2、使用循环，将输入的 N 个整数依次存储到数组 arr 中
3、获取窗口大小 M
4、初始化一个变量 windowSum 为 0，用于存储当前窗口内元素的和
5、使用一个循环，计算初始窗口大小为 M 的子数组的和，并将结果存储在 windowSum 变量中
6、将 windowSum 的值赋给变量 maxSum，作为初始的最大窗口和
7、使用另一个循环，从第 M 个元素开始，不断移动滑动窗口。在每次迭代中，更新窗口和 windowSum，通过减去窗口最左端的元素并加上窗口最右端的元素。然后，使用 Math.max 方法将 windowSum 和 maxSum 的较大值更新到 maxSum 变量中
8、循环结束后，maxSum 中存储的就是整个数组中连续子数组的和的最大值
9、最后，输出 maxSum 的值，即最大窗口和
🎉Java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(); // 输入数组的长度
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextInt(); // 输入数组元素
}
int M = scanner.nextInt(); // 窗口大小
int windowSum = 0; // 窗口内元素的和
for (int i = 0; i < M; i++) {
windowSum += arr[i]; // 计算初始窗口和
}
int maxSum = windowSum; // 初始最大窗口和
for (int i = M; i < N; i++) {
windowSum = windowSum - arr[i - M] + arr[i]; // 更新窗口和
maxSum = Math.max(maxSum, windowSum); // 更新最大窗口和
}
System.out.println(maxSum); // 输出结果
}
}
🎈Python语言思路
给定一个长度为N的数组和窗口大小M，我们需要找到滑动窗口产生的所有窗口和的最大值。
我们可以使用滑动窗口的技巧来解决这个问题。首先，我们计算数组的前M个元素的和，作为初始窗口和的值。然后，我们从第M+1个元素开始，每次向右移动一个位置，同时更新窗口和的值。
具体步骤如下：
1、输入数组的长度N和数组元素
2、输入窗口大小M
3、计算初始窗口和的值，即数组的前M个元素的和
4、初始化一个变量max_sum为初始窗口和的值
5、从第M+1个元素开始，进行以下循环：
窗口和的值减去滑出窗口的第一个元素，加上滑入窗口的下一个元素，更新窗口和的值
如果当前窗口和的值大于max_sum，则更新max_sum为当前窗口和的值
6、输出max_sum作为结果
🎉Python代码
N = int(input())
arr = list(map(int, input().split()))
M = int(input())
window_sum = sum(arr[:M])
max_sum = window_sum
for i in range(M, N):
window_sum = window_sum - arr[i - M] + arr[i]
max_sum = max(max_sum, window_sum)
print(max_sum)
作者：KJ.JK
文章出处登录后可见！
