数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++中不相邻元素的最大和 - 集2
在这个问题中，我们得到一个数组arr[]。我们的任务是创建一个程序，在C++中找到不相邻元素的最大和。
问题描述
我们需要从数组中找到序列的最大和，条件是和序列中的任意两个数字在数组中不相邻。
让我们来看一个例子来理解这个问题：
输入
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最大值是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
更新于：2020年10月15日
164 次浏览
广告