华为OD机考算法题：阿里巴巴找黄金宝箱（V）

本文主要是介绍华为OD机考算法题：阿里巴巴找黄金宝箱（V），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目部分

题目	阿里巴巴找黄金宝箱（V）
难度	易
题目说明	一贫如洗的樵夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0-N的箱子，每个箱子上面贴有一个数字。 阿里巴巴念出一个咒语数字 k ( k<N )，找出连续 k 个宝箱数字和的最大值，并输出该最大值。
输入描述	第一行输入一个数字字串，数字之间使用逗号分隔，例如: 2,10,-3,-8,40,5。 1 ≤ 字串中数字的个数 ≤ 100000。 -10000 ≤ 每个数字 ≤10000。 第二行输入咒语数字，例如: 4，咒语数字大小小于宝箱的个数。
输出描述	连续 k 个宝箱数字和的最大值，例如: 39。
补充说明	无
------------------------------------------------------
示例
示例1
输入	2,10,-3,-8,40,5
输出	39
说明	无
示例2
输入	8 1
输出	8
说明	无

---

解读与分析

题目解读：

给出 N 个数字，求出这 N 个数字中连续 k （k ≤ N）个数字之和的最大值。

分析与思路：

设数字放到数组 numArr 中从第 1 个元素 numArr[0] 开始，求出连续 k 个数字（numArr[0]、numArr[1] …… numArr[ k - 1]）之和，记录下来，设为 tmpSum。设连续 k 个数字之和最大值为 maxSum，初始复制为 maxSum = tmpSum。然后，向右滑动数字块一位，在 即 tmpSum - numArr[0] + numArr[ k ]，如果它大于 maxSum，则给 maxSum 赋新值，直至遍历完所有的数字。

此方法只需要遍历一次数组，时间复杂度为 O(n)，空间复杂度为 O(1)。

---

代码实现

Java代码

import java.util.Scanner;/*** 阿里巴巴黄金宝箱* * @since 2023.10.30* @version 0.1* @author Frank**/
public class AlibabaGoldBox5 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] inputArr = input.split(",");int[] numbers = new int[inputArr.length];for (int i = 0; i < numbers.length; i++) {numbers[i] = Integer.parseInt(inputArr[i]);}input = sc.nextLine();int k = Integer.parseInt(input);processAlibabaGoldBox5(k, numbers);}}private static void processAlibabaGoldBox5(int k, int[] numbers) {int tmpSum = 0;for (int i = 0; i < k; i++) {tmpSum += numbers[i];}int maxSum = tmpSum;for (int i = 0; i < numbers.length - k; i++) {tmpSum -= numbers[i];tmpSum += numbers[i + k ];if (tmpSum > maxSum) {maxSum = tmpSum;}}System.out.println(maxSum);}}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var inputArr = line.split(",");var numbers = new Array();for (var i = 0; i < inputArr.length; i++) {numbers[i] = parseInt(inputArr[i]);}line = await readline()var k = parseInt(line);processAlibabaGoldBox5(k, numbers);}
}();function processAlibabaGoldBox5(k, numbers) {var tmpSum = 0;for (var i = 0; i < k; i++) {tmpSum += numbers[i];}var maxSum = tmpSum;for (var i = 0; i < numbers.length - k; i++) {tmpSum -= numbers[i];tmpSum += numbers[i + k];if (tmpSum > maxSum) {maxSum = tmpSum;}}console.log(maxSum);
}

(完)

这篇关于华为OD机考算法题：阿里巴巴找黄金宝箱（V）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---