C++实现只选不相邻数的数组操作 |21xrx.com

C++实现只选不相邻数的数组操作

2023-06-24 09:39:54 深夜i -- --

C++ 数组操作只选不相邻数

在解决问题时，数组操作是计算机科学中最基本也最常用的方法之一。但在某些情况下，需要特殊的数组操作规则。例如，从一个数组中选取一些数字的问题，但要求被选取的数字不能相邻。如何在C++中实现这种数组操作呢？

首先，我们需要明确被选取的数字所在的位置，因为只有知道了数字的位置，才能判断该数字是否与其相邻。因此，我们需要定义一个数组来表示被选中的数字。假设我们的目标数组为arr，该数组的长度为n，则我们需要定义一个长度为n的布尔型数组chosen，用于记录数组arr中每个数字是否在选定列表中。

然后，我们需要编写一个函数来实现“只选不相邻数”的操作，该函数的输入参数为arr和n，输出参数为被选出的数字的和。实现方法如下：

1. 首先，我们需要定义一个长度为n的整型数组dp，用于记录当前位置i选或不选两种情况下所得到的最大和。

2. 对于任意一个arr[i]，有两种情况：选它或不选它。如果不选它，则dp[i]等于dp[i-1]；如果选它，则dp[i]等于dp[i-2]+arr[i]。因为我们不能选取相邻的数字，所以当前位置i只能选择从i-2位置转移而来。

3. 最后，我们只需要找出数组dp中的最大值，即为所求的被选中数字的和。

下面是用C++编写的实现代码：


#include <iostream>
using namespace std;
int getMaxSum(int arr[], int n) {
  int dp[n];
  dp[0] = arr[0];
  dp[1] = max(arr[0], arr[1]);
  for (int i = 2; i < n; i++) {
    dp[i] = max(dp[i-2] + arr[i], dp[i-1]);
  }
  return dp[n-1];
}
int main() {
  int arr[] = {1, 2, 3, 4, 5};
  int n = sizeof(arr) / sizeof(arr[0]);
  
  int maxSum = getMaxSum(arr, n);
  cout << "The max sum is: " << maxSum << endl;
  return 0;
}

值得注意的是，以上实现代码中的数组都是从0开始计数的。因此，在某些情况下，我们需要将数组下标加1才能正确表示数组中的位置。

总之，编写C++代码来实现“只选不相邻数”的数组操作是一项很有趣的任务。虽然思路有些难度，但只要我们善于利用数组和循环结构等基本方法，就能轻松地实现这项操作。

上一篇: idea打包java可执行jar包

下一篇: C++语言相较于其他编程语言的优点有哪些？

评论区

()

相似文章