求任意两个元素不相邻的最大和 - C++ 中的集合 2
c++server side programmingprogramming
在这个问题中，我们给定一个数组 arr[]。我们的任务是编写一个程序，用 C++ 语言求出最大和，使得任意两个元素都不相邻。
问题描述
我们需要从数组中找到一个序列的最大和，使得和序列中任意两个数字都不相邻。
让我们举个例子来理解这个问题:
输入
arr[] = {5, 1, 3, 7, 9, 2, 5}
输出
22
解释
从索引 0 开始，使用交替元素对序列求和:5 + 3 + 9 + 5 = 22 从索引 1 开始，使用交替元素对序列求和: 1 + 7 + 2 = 10
解决方案
在上一组练习中，我们已经了解了一种解决问题的方法。在这里，我们将学习使用动态规划方法解决问题。
要使用动态方法解决问题，我们需要创建一个 DP[] 数组，用于存储到当前索引的最大和。然后使用这个动态数组找到和的索引。
当前 DP 最大值是 dp[i+2]+ arr[i] 和 dp[i+1] 的最大值。
示例
编写程序来演示我们的解决方案
#include <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSumWOAdj(int arr[], int i, int n){
if (i >= n)
return 0;
if (currState[i])
return DP[i];
currState[i] = 1;
DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
return DP[i];
}
int main(){
int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
int n = sizeof(arr) / sizeof(int);
cout<<"没有两个元素相邻的最大和是 "<<calcMaxSumWOAdj(arr, 0, n);
return 0;
}
输出
没有两个元素相邻的最大和是 22
