数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中环形数组的最大和，且相邻元素不相邻
在这个问题中，我们给定一个环形数组 cirArr[]。我们的任务是创建一个程序，在 C++ 中找到环形数组中的最大和，使得没有两个元素相邻。
问题描述
对于环形数组，我们需要找到数组元素的最大和，使得相邻元素不能被选中，即我们需要选择交替的元素。
**环形数组**是一种特殊的数组，其中数组的最后一个元素连接到第一个元素。
让我们举一个例子来理解这个问题，
输入
cirArr[] = {4, 1, 5, 3, 2}输出
9
解释
最大和的环形子序列为 [4, 5, 2]。和 = 9
解决方案
问题的解决方案是使用动态规划方法来找到最大和。可以通过将环形数组视为两个数组来提取和，一个从索引 0 到 N-2，另一个从索引 1 到 n-1。这将创建两个数组，这两个数组中和的最大值将是结果。
示例
程序说明解决方案的工作原理，
#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
int DP[n];
int maxSum = 0;
for (int i = start; i < (end + 1); i++) {
DP[i] = cirArr[i];
if (maxSum < cirArr[i])
maxSum = cirArr[i];
}
for (int i = (start + 2); i < (end + 1); i++) {
for (int j = 0; j < i - 1; j++) {
if (DP[i] < DP[j] + cirArr[i]) {
DP[i] = DP[j] + cirArr[i];
if (maxSum < DP[i])
maxSum = DP[i];
}
}
}
return maxSum;
}
int findMaxSum(int cirArr[], int n){
int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n-2), n);
int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n-1), n);
int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);
return maxSum;
}
int main(){
int cirArr[] = {4, 1, 5, 3, 2};
int n = sizeof(cirArr)/sizeof(cirArr[0]);
cout<<"The maximum sum in circular array such that no two elements are adjacent is "<<findMaxSum(cirArr, n);
return 0;
}输出
The maximum sum in circular array such that no two elements are adjacent is 9
更新于: 2020-10-15
237 次浏览
广告