C ++程序中没有两个元素相邻的最大和

Z时代
2024-01-10
分类：综合

在这个问题中，我们得到了一个大小为n的数组arr []，该数组由正值组成。我们的任务是创建一个程序，以找到最大子序列和的方式，使得数组中没有两个连续的元素。

问题描述-我们需要找到具有数组元素但不能考虑数组中两个相邻元素的子数组之和。

示例

让我们举个例子来了解这个问题，

输入项

arr[] = {5, 2, 1, 9, 6}

输出结果

说明-

Subarray sum are :
{5, 1, 6}, sum = 5 + 1 + 6 = 12
{2, 9}, sum = 2 + 9 = 11

解决方法

在这里，我们将使用动态编程方法来解决该问题。用这种方法，我们将找到满足给定条件的子序列，并打印出最大的子序列。我们将创建一个数组maxSumDP [n]，该数组存储所创建子序列的最大子集。元素maxSumDP [i]存储通过将元素从索引i取到n-1而创建的子序列的最大和。为此，我们可以考虑数组arr [i]的当前元素，即maxSumDP [i] = arr [i] + maxSumDP [i + 2]。或不考虑数组arr [i]的当前元素，即maxSumDP [i] = maxSumDP [i + 2]。

算法

初始化-

maxSumDP[]

第2步-

initialize the values of maxSumDP[n−1] and maxSumDP[n−2].
maxSumDP[n−1] = arr[n−1] and maxSumDP[n−2] = max(arr[n−1], arr[n−2]).

第2步-

loop for i −> n−2 to 0

步骤1.2 -

initialize the value of maxSumDP[i],
maxSumDP[i] = maximum of (arr[i] + maxSumDP[i + 2],
maxSumDP[i + 1])

第3步-

Return maxSumDP[0] which is the maximum sum sequence sum.

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return b;
}
int calcMaxSum(int arr[], int n){
   int maxSumDP[n];
   maxSumDP[n−1] = arr[n−1];
   maxSumDP[n−2] = max(arr[n−1], arr[n−2]);
   for (int i = n − 2; i >= 0; i−−) {
      maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2],
      maxSumDP[i + 1]);
   }
   return maxSumDP[0];
}
int main() {
   int arr[] = { 5, 2 , 1, 9, 6 };
   int n = sizeof(arr) / sizeof(int);
   cout<<"最大子序列总和以使得数组中没有两个连续元素是 "<<calcMaxSum(arr, n);
   return 0;
}