資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告