使得没有两个元素相邻的最大和-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 []数组，该数组存储最大和直到当前索引。然后使用此动态数组找到总和索引。

当前的DP max是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