C++中实现只选取不相邻数的数组代码 |21xrx.com

C++中实现只选取不相邻数的数组代码

2023-06-30 21:46:24 深夜i -- --

C++ 数组不相邻数实现代码

在C++中，实现只选取不相邻数的数组代码可以帮助我们更好地掌握数组的使用。该代码可以选取数组中不相邻的元素，使得选取的元素互不相邻且和最大。

我们可以采用动态规划的思想来实现该代码。我们设dp[i]表示选取前i个元素中不相邻数的最大和。对于第i个元素，有两种情况：选或不选。若选第i个元素，则dp[i]=dp[i-2]+arr[i]；若不选第i个元素，则dp[i]=dp[i-1]。因此，我们可以得到状态转移方程：dp[i]=max(dp[i-1], dp[i-2]+arr[i])。

接下来，我们来看一下如何实现该代码。首先，我们需要定义一个动态数组来存储dp值。然后，我们需要初始化dp数组的前两个元素。接着，我们需要利用循环来遍历整个数组，计算每个dp值并更新最大的dp值。最后，我们返回dp数组中的最后一个元素，即选取不相邻数的数组的最大和。

下面是该代码的实现：


#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> arr(n);//定义数组
  for(int i=0;i<n;i++){//输入数组
    cin>>arr[i];
  }
  vector<int> dp(n);//定义dp数组
  dp[0]=arr[0];//初始化dp数组前两个元素
  dp[1]=max(arr[0], arr[1]);
  for(int i=2;i<n;i++){//动态规划求解dp值
    dp[i]=max(dp[i-1], dp[i-2]+arr[i]);
  }
  cout<<dp[n-1]<<endl;//返回最大和
  return 0;
}

在使用该代码时，我们需要为该数组输入元素。例如，当输入数组为{3, 2, 5, 10, 7}时，该代码的返回值为15，即选取3和10两个元素使其不相邻的和最大。

总之，通过以上的介绍，我们可以更好地掌握C++中实现只选取不相邻数的数组代码的方法和思路。它是一种常用的算法，在实际的编程过程中可以帮助我们更加高效地解决问题。

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

下一篇: C++大小端转换教程

评论区

()

相似文章