【华为OD题库-105】滑动窗口最大值-java
2023-12-21 12:37:15
题目
题目描述:
有一个N个整数的数组,和一个长度为M的窗口,窗口从数组内的第一个数开始滑动直到窗口不能滑动为止,每次窗口滑动产生一个窗口和(窗口内所有数的和),求窗口滑动产生的所有窗口和的最大值。
输入描述:
第一行输入一个正整数N,表示整数个数。(O<N<100000)第二行输入N个整数,整数的取值范围为[-100,100]。
第三行输入一个正整数M,M代表窗口的大小,M<=100000,且M<=N。
输出描述:
窗口滑动产生所有窗口和的最大值口。
示例1
输入输出示例仅供调试,后台判题数据一般不包含示例
输入
6
12 10 20 30 15 23
3
输出
68
思路
简单题,遍历窗口右边界,根据窗口长度计算左边界,当左边界大于0时,窗口累加和计算时就要开始减去左边的值(res-nums[i-1])
遍历完成后即可得到滑动窗口的最大值
题解
package hwod;
import java.util.Scanner;
public class SlidingWin {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int size = sc.nextInt();
System.out.println(slidingWin(nums,size));
}
private static int slidingWin(int[] nums, int size) {
int res = 0, max = 0;
for (int j = 0; j < nums.length; j++) {
int i = j - size + 1;
res += nums[j];
if(i>0) {
res -= nums[i-1];
}
max = Math.max(max, res);
}
return max;
}
}
推荐
如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。
说明
本专栏所有文章均为原创,欢迎转载,请注明文章出处:https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信,搜索请谨慎鉴别。技术类文章一般都有时效性,本人习惯不定期对自己的博文进行修正和更新,因此请访问出处以查看本文的最新版本。
文章来源:https://blog.csdn.net/qq_31076523/article/details/135127020
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!