資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中求最大和，且任意兩個元素不相鄰
在這個問題中，我們給定一個數組 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
解決方案
為了解決這個問題，我們將簡單地遍歷陣列的所有元素，並維護兩個和：sumVar1 和 sumVar2。sumVar1 將包含包含當前元素的和，而 sumVar2 將包含不包含當前元素的和。
在每次迭代中，我們將 sumVar2 更新為 max(sumVar1, sumVar2)。然後更新 sumVar1。在迴圈結束時，sumVar2 將給出所需的和。
示例
程式演示了我們解決方案的工作原理：
#include<iostream>
using namespace std;
int findmaximum(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxSumWOAdjecent(int arr[], int N){
int maxSum1 = arr[0];
int maxSum2 = 0;
int temp;
for (int i = 1; i < N; i++) {
temp = findmaximum(maxSum1, maxSum2);
maxSum1 = maxSum2 + arr[i];
maxSum2 = temp;
}
return (findmaximum(maxSum1, maxSum2));
}
int main(){
int arr[] = {5, 1, 3, 7, 9, 2, 5};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum such that no two elements are adjacent is "<<findMaxSumWOAdjecent(arr, N);
return 0;
}輸出
The maximum sum such that no two elements are adjacent is 22
更新於：2020年10月15日
189 次瀏覽
廣告