【华为机试】2023年真题B卷（python）-滑动窗口最大值

一、题目

题目描述：

有一个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

四、要求

时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++262144K，其他语言524288K

五、解题思路

这个问题可以使用滑动窗口的方法来解决。我们可以维护一个窗口，窗口的大小为M。初始时，窗口从数组的第一个数开始滑动。

首先，我们计算初始窗口内所有数的和，记为current_sum。

然后，我们依次将窗口向右滑动，每次滑动时，将窗口右边的数加入窗口，同时将窗口左边的数移出窗口。我们更新current_sum为新窗口内所有数的和。

在每次滑动时，我们比较current_sum与当前最大窗口和的值，如果current_sum更大，则更新最大窗口和的值。

最后，当窗口无法再滑动时，返回最大窗口和作为结果。

六、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-滑动窗口最大值.py
@Time    :   2023/12/29 19:38:15
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

def max_window_sum(N, nums, M):
    if N <= 0 or M <= 0 or M > N:
        return None

    # 计算初始窗口内所有数的和
    current_sum = sum(nums[:M])
    max_sum = current_sum

    # 滑动窗口
    for i in range(M, N):
        current_sum = current_sum - nums[i - M] + nums[i]
        max_sum = max(max_sum, current_sum)

    return max_sum

# 读取输入
N = int(input())
nums = list(map(int, input().split()))
M = int(input())

# 计算最大窗口和
result = max_window_sum(N, nums, M)
print(result)