假设给定一串数字{1,1,4,2,6,8,5},我们要从中选择若干个数,使最后的和达到最大。选择的规则是,不能选相邻的数字。比如:如果我们选了第一个数字1,那么我们就不能选,如果我们选择了数字4,那么我们就不能选择与它相邻的1和2。生成一个c++代码
时间: 2024-11-05 15:32:30 浏览: 21
为了实现这个功能,你可以使用动态规划(Dynamic Programming)算法,特别是滑动窗口的概念。以下是一个简单的C++代码示例:
```cpp
#include <iostream>
#include <vector>
int maxSumNoAdjacent(int arr[], int n) {
if (n <= 0) return 0;
std::vector<int> dp(n);
dp[0] = arr[0]; // 第一个数本身就是最优解
for (int i = 1; i < n; ++i) {
if (i - 2 >= 0) dp[i] = std::max(dp[i], dp[i - 2] + arr[i]); // 如果可以跳过两个,就取最大值
else dp[i] = std::max(dp[i], dp[i - 1] + arr[i]); // 否则只能跳过一个
}
return dp[n - 1];
}
int main() {
int numbers[] = {1, 1, 4, 2, 6, 8, 5};
int n = sizeof(numbers) / sizeof(numbers[0]);
std::cout << "最大和为: " << maxSumNoAdjacent(numbers, n) << "\n";
return 0;
}
```
这段代码定义了一个`maxSumNoAdjacent`函数,它接受一个整数数组和其长度作为输入。通过迭代数组,它构建了一个动态规划表,其中每个dp[i]表示从开始到位置i的最大和,不包括当前位置及其相邻位置的元素。
阅读全文