使得没有两个元素相邻的最大和-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 夜雨祝福语简短10字