資料結構
網路
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 次瀏覽
廣告