??個(gè)人博客首頁(yè)： KJ.JK
?
??專欄介紹： 定期更新華為OD各個(gè)時(shí)間階段的機(jī)試真題，每日定時(shí)更新，本專欄每篇的文章都會(huì)將使用C++、Python、Java三種語(yǔ)言進(jìn)行更新解答，每個(gè)題目的思路分析都非常詳細(xì)，超過百字歡迎大家訂閱學(xué)習(xí)，代碼可以直接運(yùn)行使用
一、題目
??題目描述
有一個(gè)N個(gè)整數(shù)的數(shù)組，和一個(gè)長(zhǎng)度為M的窗口，窗口從數(shù)組內(nèi)的第一個(gè)數(shù)開始滑動(dòng)直到窗口不能滑動(dòng)為止，
?
每次窗口滑動(dòng)產(chǎn)生一個(gè)窗口和（窗口內(nèi)所有數(shù)的和），求窗口滑動(dòng)產(chǎn)生的所有窗口和的最大值
??輸入輸出
輸入
第一行輸入一個(gè)正整數(shù)N，表示整數(shù)個(gè)數(shù)。（0<N<100000）
第二行輸入N個(gè)整數(shù)，整數(shù)的取值范圍為[-100,100]。
第三行輸入一個(gè)正整數(shù)M，M代表窗口的大小，M<=100000，且M<=N。
?
輸出
窗口滑動(dòng)產(chǎn)生所有窗口和的最大值
??樣例1
輸入
6
12 10 20 30 15 23
3
輸出
68
說明
窗口長(zhǎng)度為3，窗口滑動(dòng)產(chǎn)生的窗口和分別為10+20+30=60，20+30+15=65，30+15+23=68，15+23+12=50，
所以窗口滑動(dòng)產(chǎn)生的所有窗口和的最大值為68
二、代碼與思路參考
??C++語(yǔ)言思路
1、讀取輸入的整數(shù)N，表示數(shù)組的長(zhǎng)度
2、讀取輸入的整數(shù)數(shù)組元素，將其存儲(chǔ)在一個(gè)名為arr的向量中
3、讀取輸入的整數(shù)M，表示滑動(dòng)窗口的長(zhǎng)度
4、初始化變量window_sum為前M個(gè)元素的和，即窗口的初始和
5、初始化變量max_sum為window_sum，表示當(dāng)前的最大和
6、從M開始，通過遍歷數(shù)組來移動(dòng)滑動(dòng)窗口
- 在每個(gè)位置i，通過將窗口最左邊的元素移出窗口并將窗口最右邊的元素移入窗口，更新window_sum的值
- 檢查window_sum是否大于max_sum，如果是，則將max_sum更新為window_sum
7、遍歷完成后，max_sum將包含滑動(dòng)窗口的最大和
8、輸出max_sum作為結(jié)果
??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]; // 輸入數(shù)組元素
}
int M;
cin >> M; // 輸入M
int window_sum = 0;
for (int i = 0; i < M; i++) {
window_sum += arr[i]; // 計(jì)算初始窗口和
}
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語(yǔ)言思路
1、首先，從輸入中獲取數(shù)組的長(zhǎng)度 N，并創(chuàng)建一個(gè)大小為 N 的整數(shù)數(shù)組 arr
2、使用循環(huán)，將輸入的 N 個(gè)整數(shù)依次存儲(chǔ)到數(shù)組 arr 中
3、獲取窗口大小 M
4、初始化一個(gè)變量 windowSum 為 0，用于存儲(chǔ)當(dāng)前窗口內(nèi)元素的和
5、使用一個(gè)循環(huán)，計(jì)算初始窗口大小為 M 的子數(shù)組的和，并將結(jié)果存儲(chǔ)在 windowSum 變量中
6、將 windowSum 的值賦給變量 maxSum，作為初始的最大窗口和
7、使用另一個(gè)循環(huán)，從第 M 個(gè)元素開始，不斷移動(dòng)滑動(dòng)窗口。在每次迭代中，更新窗口和 windowSum，通過減去窗口最左端的元素并加上窗口最右端的元素。然后，使用 Math.max 方法將 windowSum 和 maxSum 的較大值更新到 maxSum 變量中
8、循環(huán)結(jié)束后，maxSum 中存儲(chǔ)的就是整個(gè)數(shù)組中連續(xù)子數(shù)組的和的最大值
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(); // 輸入數(shù)組的長(zhǎng)度
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextInt(); // 輸入數(shù)組元素
}
int M = scanner.nextInt(); // 窗口大小
int windowSum = 0; // 窗口內(nèi)元素的和
for (int i = 0; i < M; i++) {
windowSum += arr[i]; // 計(jì)算初始窗口和
}
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); // 輸出結(jié)果
}
}
??Python語(yǔ)言思路
給定一個(gè)長(zhǎng)度為N的數(shù)組和窗口大小M，我們需要找到滑動(dòng)窗口產(chǎn)生的所有窗口和的最大值。
我們可以使用滑動(dòng)窗口的技巧來解決這個(gè)問題。首先，我們計(jì)算數(shù)組的前M個(gè)元素的和，作為初始窗口和的值。然后，我們從第M+1個(gè)元素開始，每次向右移動(dòng)一個(gè)位置，同時(shí)更新窗口和的值。
具體步驟如下：
1、輸入數(shù)組的長(zhǎng)度N和數(shù)組元素
2、輸入窗口大小M
3、計(jì)算初始窗口和的值，即數(shù)組的前M個(gè)元素的和
4、初始化一個(gè)變量max_sum為初始窗口和的值
5、從第M+1個(gè)元素開始，進(jìn)行以下循環(huán)：文章來源：http://www.zghlxwxcb.cn/news/detail-715151.html
窗口和的值減去滑出窗口的第一個(gè)元素，加上滑入窗口的下一個(gè)元素，更新窗口和的值
如果當(dāng)前窗口和的值大于max_sum，則更新max_sum為當(dāng)前窗口和的值
6、輸出max_sum作為結(jié)果文章來源地址http://www.zghlxwxcb.cn/news/detail-715151.html
??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
到了這里，關(guān)于【華為OD機(jī)試真題 C++ Java Python】1、滑動(dòng)窗口最大值 | 機(jī)試真題+思路參考+代碼解析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
