返回目录

题目描述

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

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

输入描述

第一行为数组numbers的长度

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

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

输出描述

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

示例：

题目解析

本题我第一个思路是通过分支递归+缓存优化求解

但是经过测试，1 ≤ numbers.length ≤ 100000 数量级下，递归操作会StackOverflow，缓存cache数组占用的内存会超出限制。

后面思考了一下，无论我们怎么选，左边选择的，以及右边选择的，必然都是连续的，且是从头尾开始的连续，即不可出现下面情况：

因此，本题其实可以简化为，将n次分解为左边选择的个数，以及右边选择的个数。

以用例1画图示：

初始时，假设左边选择了0个，右边选择了n=3个，（黄色部分代表选择）：

之后，左边选择1个，右边选择2个

之后，左边选择2，右边选择1个

最后，左边选择3个，右边选择0个

Python算法源码

def main():
    len_val = int(input())
    nums = list(map(int, input().split()))
    n = int(input())

    print(getResult(len_val, nums, n))


def getResult(len_val, nums, n):
    # 初始时，左边选择0个，因此左边选择的香蕉数为 0
    left_sum = 0

    # 初始时，右边选择n个，因此右边选择的香蕉数为 nums[len-n:] 这个n个元素之和
    right_sum = sum(nums[len_val - n:])

    # 如果选择数n == len，即全选，此时直接返回初始right_sum
    if len_val == n:
        return right_sum

    # 如果不是全选
    # sum记录当前选择结果
    sum_val = left_sum + right_sum
    # ans记录所有选择结果中最大的
    ans = sum_val

    # l指向左边将要获得的，即左边获得一个
    l = 0
    # r指向右边将要失去的，即右边失去一个
    r = len_val - n

    while l < n:
        sum_val += nums[l] - nums[r]
        ans = max(ans, sum_val)
        l += 1
        r += 1

    return ans


if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

int getResult(int len, int *nums, int n) {
    // 初始时，左边选择0个，因此左边选择的香蕉数为 0
    int leftSum = 0;

    // 初始时，右边选择n个，因此右边选择的香蕉数为 nums[len-n] ~ nums[len - 1] 这个n个元素之和
    int rightSum = 0;
    for (int i = len - n; i < len; i++) {
        rightSum += nums[i];
    }

    // 如果选择数n == len，即全选，此时直接返回初始rightSum
    if (len == n) {
        return rightSum;
    }

    // 如果不是全选
    // sum记录当前选择结果
    int sum = leftSum + rightSum;
    // ans记录所有选择结果中最大的
    int ans = sum;

    // l指向左边将要获得的，即左边获得一个
    int l = 0;
    // r指向右边将要失去的，即右边失去一个
    int r = len - n;

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

    return ans;
}

int main() {
    int len;
    scanf("%d", &len);

    int *nums = (int *)malloc(len * sizeof(int));
    for (int i = 0; i < len; i++) {
        scanf("%d", &nums[i]);
    }

    int n;
    scanf("%d", &n);

    printf("%d\n", getResult(len, nums, n));

    free(nums); // Freeing dynamically allocated memory

    return 0;
}

java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int len = Integer.parseInt(sc.nextLine());
        String[] numsInput = sc.nextLine().split(" ");
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = Integer.parseInt(numsInput[i]);
        }
        int n = Integer.parseInt(sc.nextLine());

        System.out.println(getResult(len, nums, n));
    }

    public static int getResult(int len, int[] nums, int n) {
        // 初始时，左边选择0个，因此左边选择的香蕉数为 0
        int leftSum = 0;

        // 初始时，右边选择n个，因此右边选择的香蕉数为 nums[len-n] ~ nums[len - 1] 这个n个元素之和
        int rightSum = 0;
        for (int i = len - n; i < len; i++) {
            rightSum += nums[i];
        }

        // 如果选择数n == len，即全选，此时直接返回初始rightSum
        if (len == n) {
            return rightSum;
        }

        // 如果不是全选
        // sum记录当前选择结果
        int sum = leftSum + rightSum;
        // ans记录所有选择结果中最大的
        int ans = sum;

        // l指向左边将要获得的，即左边获得一个
        int l = 0;
        // r指向右边将要失去的，即右边失去一个
        int r = len - n;

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

        return ans;
    }
}