华为OD机试真题 - 贪吃的猴子 (D卷,200分)

题目描述

一只贪吃的猴子，来到一个果园，发现许多串香蕉排成一行，每串香蕉上有若干根香蕉。每串香蕉的根数由数组numbers给出。

猴子获取香蕉，每次都只能从行的开头或者末尾获取，并且只能获取N次，求猴子最多能获取多少根香蕉。

目录

题目描述

输入描述

输出描述

用例

题目解析

Java算法源码

JS算法源码

Python算法源码

C算法源码

华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作

https://ac.nowcoder.com/acm/contest/5652/K

点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。

输入描述

第一行为数组numbers的长度

第二行为数组numbers的值每个数字通过空格分开

第三行输入为N，表示获取的次数

输出描述

按照题目要求能获取的最大数值

备注

• 1 ≤ numbers.length ≤ 100000
• 1 ≤ numbers ≤ 100
• 1 ≤ N ≤ numbers.length

用例

题目解析

1. 首先，我们需要计算从行的开头和末尾获取香蕉的最大值。可以使用动态规划的方法，定义一个数组dp，其中dp[i]表示从前i个位置中能获取到的最大香蕉数。
2. 初始化dp数组，dp[0] = numbers[0]，dp[1] = max(numbers[0], numbers[1])。
3. 遍历数组numbers，对于每个位置i，有两种选择：从行的开头获取或者从行的末尾获取。因此，dp[i] = max(dp[i-2] + numbers[i], dp[i-1])。
4. 最后，返回dp数组的最后一个元素，即为猴子最多能获取的香蕉数。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const len = parseInt(await readline());
  const nums = (await readline()).split(" ").map(Number);
  const n = parseInt(await readline());

  console.log(getResult(len, nums, n));
})();

function getResult(len, nums, n) {
  let leftSum = 0;

  let rightSum = 0;
  for (let i = len - n; i < len; i++) {
    rightSum += nums[i];
  }

  if (len == n) {
    return rightSum;
  }

  let sum = leftSum + rightSum;
  let ans = sum;

  let l = 0;
  let r = len - n;

  while (l < n) {
    sum += nums[l++] - nums[r++];
    ans = Math.max(ans, sum);
  }

  return ans;
}

Java算法源码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader