使得没有两个元素相邻的最大和-C ++中的Set 2
在这个问题中，我们得到了一个数组arr[]。我们的任务是创建一个程序来查找最大和，以使C++中没有两个相邻的元素。
问题描述
我们需要从数组中找到序列的最大和，以使总和序列中没有2个数字在数组中相邻。
让我们举个例子来了解这个问题，
输入值
arr[] = {5, 1, 3, 7, 9, 2, 5}输出结果
22
说明
Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22 Taking sum sequence from index 1 with alternate elements : 1 + 7 + 2 = 10
解决方法
在上一组中，我们看到了一种解决问题的方法。在这里，我们将学习解决问题的动态编程方法。
为了使用动态方法解决问题，我们需要创建一个DP[]数组，该数组存储最大和直到当前索引。然后使用此动态数组找到总和索引。
当前的DPmax是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<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
return 0;
}输出结果
The maximum sum such that no two elements are adjacent is 22
热门推荐
10 祝女儿简短祝福语大全
11 大学新年祝福语简短创意
12 元旦适合的祝福语简短
13 朋友出远门祝福语简短
14 初六简短的祝福语
15 祝男孩生日祝福语简短
16 同事调离的祝福语简短
17 拜年红包的祝福语简短
18 妈妈生日祝福语简短励志