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

2024-01-01 13:53:12

一、题目

题目描述:

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

文章来源:https://blog.csdn.net/u014481728/article/details/135297468
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。