C++ 中求循环数组中任意两个元素不相邻的最大和
c++server side programmingprogramming
本题中给定一个循环数组 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<<"圆形阵列中任意两个元素不相邻的最大和为 "<<findMaxSum(cirArr, n);
return 0;
}
输出
圆形阵列中任意两个元素不相邻的最大和为 9
