贪吃的猴子 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

一只贪吃的猴子，来到一个果园，发现许多串香蕉排成一行，每串香蕉上有若干根香蕉。每串香蕉的根数由数组numbers给出。猴子获取香蕉，每次都只能从行的开头或者末尾获取，并且只能获取N次，求猴子最多能获取多少根香蕉。

输入描述

第一行为数组numbers的长度

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

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

输出描述

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

示例1

输入
7
1 2 2 7 3 6 1
3

输出
10

示例2

输入
3
1 2 3
3

输出
6

说明
全部获取所有的香蕉，因此最终根数为1+2+3 = 6

示例3

输入
4
4 2 2 3
2

输出
7

说明
第一次获取香蕉为行的开头，第二次获取为行的末尾，因此最终根数为4+3 =7

备注

1<= numbers.length <= 100000

1<= numbers <= 100

1 <= N <= numbers.length

题解

这是一道数组和双指针的题目，需要通过双指针的方式在数组中找到最优解。

解题思路:

双指针的思路是通过两个指针（在这里是 l 和 r）从两端向中间移动，通过不断的调整两边的元素选取个数，找到最佳结果。在这个问题中，通过调整左右两边的选取次数，计算获取香蕉的总数。

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> numbers(n);
    for(int i=0; i<n; i++) cin >> numbers[i];

    int N;
    cin >> N;
    int tot = 0;
    for(int i=0; i<N; i++) tot += numbers[i];

    int rs = tot;

    int l = N-1, r = n-1;
    while(l >= 0) {
        tot += numbers[r--] - numbers[l--];
        rs = max(rs, tot);
    }

    cout << rs << endl;

    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] numbers = Arrays.stream(new int[n]).map(i -> in.nextInt()).toArray();
        int N = in.nextInt();

        // 左边选N个， 右侧选0个
        int tot = Arrays.stream(numbers, 0, N).sum();

        int rs = tot;
        int l = N - 1, r = n - 1;

        // 不断的尝试调整两边的元素选取个数, 找到最佳结果
        while (l >= 0) {
            tot += numbers[r--] - numbers[l--];
            rs = Math.max(rs, tot);
        }
        System.out.println(rs);
    }
}

以上题解给我一些总结性的描述，从以下几点方面：题目类型，解题思路，代码大致描述，时间复杂度，空间复杂度，及相关知识点

Python

n = int(input())
numbers = list(map(int, input().split()))
N = int(input())

tot = sum(numbers[i] for i in range(N))
rs = tot

r = n - 1
for l in range(N-1, -1, -1):
    tot += numbers[r] - numbers[l]
    rs = max(rs, tot)
    r -= 1

print(rs)