【华为OD】贪吃的猴子

题目描述

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

输入描述

第一行为数组 numbers 的长度
第二行为数组 numbers 的值，每个数字通过空格分开
第三行输入为 N，表示获取的次数

约束条件：

• 1 <= numbers.length <= 100000
• 1 <= numbers[i] <= 100
• 1 <= N <= numbers.length

输出描述

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

示例

示例一

输入：

7
1 2 2 7 3 6 1
3

输出：

10

说明：
第一次获取香蕉，无论是从行的开头或者末尾获取，得到的香蕉根数目为1。但是，从行末尾获取能获取到最优的策略，后面可以直接得到香蕉根数目 6和3。因此最终根数为 1+6+3=10

示例二

输入：

7
2 2 2 7 3 6 1
3

输出：

10

解题思路

这是一个典型的滑动窗口问题。猴子只能从数组的两端取元素，取N次，要求最大和。

核心思想：

1. 猴子取N个元素，这N个元素必定是数组两端的连续子数组的组合
2. 可以枚举从左端取i个，从右端取(N-i)个的所有情况
3. 使用前缀和优化计算效率

关键概念：

• 前缀和：预计算数组前缀和，快速计算任意区间和
• 枚举策略：枚举从左端取的个数，剩余从右端取
• 边界处理：注意取0个和取N个的边界情况

我将提供两种解法：前缀和枚举法和滑动窗口法。

解法一：前缀和枚举法

通过预计算前缀和，枚举所有可能的取法组合，找到最大值。

Java实现

import java.util.*;public class Solution1 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int len = sc.nextInt();int[] numbers = new int[len];for (int i = 0; i < len; i++) {numbers[i] = sc.nextInt();}int n = sc.nextInt();int result = maxBananas(numbers, n);System.out.println(result);sc.close();}private static int maxBananas(int[] numbers, int n) {int len = numbers.length;// 计算前缀和int[] prefixSum = new int[len + 1];for (int i = 0; i < len; i++) {prefixSum[i + 1] = prefixSum[i] + numbers[i];}int maxSum = 0;// 枚举从左端取i个，从右端取(n-i)个for (int i = 0; i <= n; i++) {int leftSum = 0;int rightSum = 0;// 从左端取i个if (i > 0) {leftSum = prefixSum[i];}// 从右端取(n-i)个int rightCount = n - i;if (rightCount > 0) {rightSum = prefixSum[len] - prefixSum[len - rightCount];}maxSum = Math.max(maxSum, leftSum + rightSum);}return maxSum;}
}

Python实现

def max_bananas(numbers, n):length = len(numbers)# 计算前缀和prefix_sum = [0] * (length + 1)for i in range(length):prefix_sum[i + 1] = prefix_sum[i] + numbers[i]max_sum = 0# 枚举从左端取i个，从右端取(n-i)个for i in range(n + 1):left_sum = 0right_sum = 0# 从左端取i个if i > 0:left_sum = prefix_sum[i]# 从右端取(n-i)个right_count = n - iif right_count > 0:right_sum = prefix_sum[length] - prefix_sum[length - right_count]max_sum = max(max_sum, left_sum + right_sum)return max_sumdef solve_prefix_sum():length = int(input())numbers = list(map(int, input().split()))n = int(input())result = max_bananas(numbers, n)print(result)solve_prefix_sum()

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int maxBananas(vector<int>& numbers, int n) {int len = numbers.size();// 计算前缀和vector<int> prefixSum(len + 1, 0);for (int i = 0; i < len; i++) {prefixSum[i + 1] = prefixSum[i] + numbers[i];}int maxSum = 0;// 枚举从左端取i个，从右端取(n-i)个for (int i = 0; i <= n; i++) {int leftSum = 0;int rightSum = 0;// 从左端取i个if (i > 0) {leftSum = prefixSum[i];}// 从右端取(n-i)个int rightCount = n - i;if (rightCount > 0) {rightSum = prefixSum[len] - prefixSum[len - rightCount];}maxSum = max(maxSum, leftSum + rightSum);}return maxSum;
}int main() {int len;cin >> len;vector<int> numbers(len);for (int i = 0; i < len; i++) {cin >> numbers[i];}int n;cin >> n;int result = maxBananas(numbers, n);cout << result << endl;return 0;
}

解法二：滑动窗口法

使用滑动窗口的思想，先取前N个元素，然后逐步调整窗口位置。

Java实现

import java.util.*;public class Solution2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int len = sc.nextInt();int[] numbers = new int[len];for (int i = 0; i < len; i++) {numbers[i] = sc.nextInt();}int n = sc.nextInt();int result = maxBananasSliding(numbers, n);System.out.println(result);sc.close();}private static int maxBananasSliding(int[] numbers, int n) {int len = numbers.length;// 先计算取前n个元素的和int currentSum = 0;for (int i = 0; i < n; i++) {currentSum += numbers[i];}int maxSum = currentSum;// 滑动窗口：逐步将左端元素替换为右端元素for (int i = 0; i < n; i++) {// 移除左端第(n-1-i)个元素，添加右端第(len-1-i)个元素currentSum = currentSum - numbers[n - 1 - i] + numbers[len - 1 - i];maxSum = Math.max(maxSum, currentSum);}return maxSum;}
}

Python实现

def max_bananas_sliding(numbers, n):length = len(numbers)# 先计算取前n个元素的和current_sum = sum(numbers[:n])max_sum = current_sum# 滑动窗口：逐步将左端元素替换为右端元素for i in range(n):# 移除左端第(n-1-i)个元素，添加右端第(length-1-i)个元素current_sum = current_sum - numbers[n - 1 - i] + numbers[length - 1 - i]max_sum = max(max_sum, current_sum)return max_sumdef solve_sliding_window():length = int(input())numbers = list(map(int, input().split()))n = int(input())result = max_bananas_sliding(numbers, n)print(result)solve_sliding_window()

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int maxBananasSliding(vector<int>& numbers, int n) {int len = numbers.size();// 先计算取前n个元素的和int currentSum = 0;for (int i = 0; i < n; i++) {currentSum += numbers[i];}int maxSum = currentSum;// 滑动窗口：逐步将左端元素替换为右端元素for (int i = 0; i < n; i++) {// 移除左端第(n-1-i)个元素，添加右端第(len-1-i)个元素currentSum = currentSum - numbers[n - 1 - i] + numbers[len - 1 - i];maxSum = max(maxSum, currentSum);}return maxSum;
}int main() {int len;cin >> len;vector<int> numbers(len);for (int i = 0; i < len; i++) {cin >> numbers[i];}int n;cin >> n;int result = maxBananasSliding(numbers, n);cout << result << endl;return 0;
}

解法三：优化的动态规划法

使用动态规划的思想，记录每种取法的最优解。

Java实现

import java.util.*;public class Solution3 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int len = sc.nextInt();int[] numbers = new int[len];for (int i = 0; i < len; i++) {numbers[i] = sc.nextInt();}int n = sc.nextInt();int result = maxBananasDP(numbers, n);System.out.println(result);sc.close();}private static int maxBananasDP(int[] numbers, int n) {int len = numbers.length;// leftSum[i] 表示从左端取i个元素的和int[] leftSum = new int[n + 1];for (int i = 1; i <= n; i++) {leftSum[i] = leftSum[i - 1] + numbers[i - 1];}// rightSum[i] 表示从右端取i个元素的和int[] rightSum = new int[n + 1];for (int i = 1; i <= n; i++) {rightSum[i] = rightSum[i - 1] + numbers[len - i];}int maxSum = 0;for (int i = 0; i <= n; i++) {maxSum = Math.max(maxSum, leftSum[i] + rightSum[n - i]);}return maxSum;}
}

Python实现

def max_bananas_dp(numbers, n):length = len(numbers)# left_sum[i] 表示从左端取i个元素的和left_sum = [0] * (n + 1)for i in range(1, n + 1):left_sum[i] = left_sum[i - 1] + numbers[i - 1]# right_sum[i] 表示从右端取i个元素的和right_sum = [0] * (n + 1)for i in range(1, n + 1):right_sum[i] = right_sum[i - 1] + numbers[length - i]max_sum = 0for i in range(n + 1):max_sum = max(max_sum, left_sum[i] + right_sum[n - i])return max_sumdef solve_dp():length = int(input())numbers = list(map(int, input().split()))n = int(input())result = max_bananas_dp(numbers, n)print(result)solve_dp()

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int maxBananasDP(vector<int>& numbers, int n) {int len = numbers.size();// leftSum[i] 表示从左端取i个元素的和vector<int> leftSum(n + 1, 0);for (int i = 1; i <= n; i++) {leftSum[i] = leftSum[i - 1] + numbers[i - 1];}// rightSum[i] 表示从右端取i个元素的和vector<int> rightSum(n + 1, 0);for (int i = 1; i <= n; i++) {rightSum[i] = rightSum[i - 1] + numbers[len - i];}int maxSum = 0;for (int i = 0; i <= n; i++) {maxSum = max(maxSum, leftSum[i] + rightSum[n - i]);}return maxSum;
}int main() {int len;cin >> len;vector<int> numbers(len);for (int i = 0; i < len; i++) {cin >> numbers[i];}int n;cin >> n;int result = maxBananasDP(numbers, n);cout << result << endl;return 0;
}

算法复杂度分析

解法一：前缀和枚举法

• 时间复杂度：O(N + K)，其中N是数组长度，K是取的次数
• 空间复杂度：O(N)，存储前缀和数组

解法二：滑动窗口法

• 时间复杂度：O(N + K)，初始化窗口O(K)，滑动窗口O(K)
• 空间复杂度：O(1)，只使用常数额外空间

解法三：优化的动态规划法

• 时间复杂度：O(K)，只需要计算左右两端的累积和
• 空间复杂度：O(K)，存储左右累积和数组

算法原理详解

核心思想

这个问题的本质是在数组两端选择K个元素使和最大。关键洞察：

1. 选择的K个元素必定是左端连续i个 + 右端连续(K-i)个的组合
2. 需要枚举所有可能的i值（0 ≤ i ≤ K）
3. 使用前缀和或滑动窗口优化计算效率

三种解法的特点

1. 前缀和枚举法：

   • 思路直观，易于理解
   • 预计算前缀和，快速计算区间和
   • 适合理解问题本质

2. 滑动窗口法：

   • 空间效率最高
   • 通过窗口滑动避免重复计算
   • 代码相对复杂，但效率高

3. 动态规划法：

   • 分别计算左右两端的累积和
   • 逻辑清晰，代码简洁
   • 时间复杂度最优

示例分析

示例一详细分析

数组：[1, 2, 2, 7, 3, 6, 1]，N = 3

所有可能的取法：

1. 左端取0个，右端取3个：0 + (3+6+1) = 10
2. 左端取1个，右端取2个：1 + (6+1) = 8
3. 左端取2个，右端取1个：(1+2) + 1 = 4
4. 左端取3个，右端取0个：(1+2+2) + 0 = 5

最大值为10，对应策略：从右端取3个元素(3,6,1)。

图示表示

数组: [1, 2, 2, 7, 3, 6, 1]↑           ↑  ↑  ↑可能取      最优策略：取这3个策略枚举：
- 取法1: [] + [3,6,1] = 10 ✓ (最优)
- 取法2: [1] + [6,1] = 8
- 取法3: [1,2] + [1] = 4  
- 取法4: [1,2,2] + [] = 5

优化技巧

1. 边界条件优化

// 特殊情况：如果N等于数组长度，直接返回所有元素和
if (n == numbers.length) {return Arrays.stream(numbers).sum();
}

2. 提前终止优化

// 如果当前和已经是理论最大值，可以提前终止
if (currentSum == totalSum) {return currentSum;
}

3. 空间优化

// 滑动窗口法不需要额外的数组空间
// 只需要维护当前窗口的和
int windowSum = 0;
for (int i = 0; i < n; i++) {windowSum += numbers[i];
}

扩展应用

1. 股票买卖问题

可以应用于股票交易中选择最优的买卖时机。

2. 游戏策略问题

在游戏中选择最优的行动策略，最大化收益。

3. 资源分配问题

在有限的操作次数内，选择最优的资源获取策略。

常见错误

1. 边界处理错误

// 错误：没有考虑取0个的情况
for (int i = 1; i <= n; i++) { // 应该从0开始// ...
}// 正确：
for (int i = 0; i <= n; i++) {// ...
}

2. 索引计算错误

// 错误：右端索引计算错误
rightSum = prefixSum[len] - prefixSum[len - rightCount - 1]; // 多减了1// 正确：
rightSum = prefixSum[len] - prefixSum[len - rightCount];

3. 滑动窗口更新错误

// 错误：窗口更新逻辑错误
currentSum = currentSum - numbers[i] + numbers[len - 1 - i]; // 索引错误// 正确：
currentSum = currentSum - numbers[n - 1 - i] + numbers[len - 1 - i];

总结

三种解法都能正确解决问题，选择建议：

1. 前缀和枚举法：

   • 思路最直观，易于理解和实现
   • 适合初学者和面试场景
   • 推荐用于学习和理解问题

2. 滑动窗口法：

   • 空间效率最高，只需O(1)额外空间
   • 适合内存受限的场景
   • 推荐用于性能要求高的场景

3. 动态规划法：

   • 时间复杂度最优O(K)
   • 代码简洁，逻辑清晰
   • 推荐用于竞赛和实际应用

核心要点：

• 理解问题的本质：在数组两端选择元素
• 掌握枚举所有可能组合的方法
• 使用前缀和或滑动窗口优化计算
• 注意边界条件的处理

对于华为OD机试，建议掌握前缀和枚举法，因为它最容易理解和实现，不容易出错，且能很好地展示对问题的理解。