資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最大和，使得沒有兩個元素相鄰 C++ 程式中的另一種方法
在這個問題中，我們給定一個大小為 n 的陣列 arr[]，其中包含正值。我們的任務是建立一個程式來找到最大子序列和，方法是使陣列中沒有兩個連續的元素。
問題描述 - 我們需要找到子陣列的和，該子陣列包含陣列的元素，但不能考慮陣列的任何兩個相鄰元素。
示例
讓我們舉一個例子來理解這個問題，
輸入
arr[] = {5, 2, 1, 9, 6}輸出
解釋 -
Subarray sum are :
{5, 1, 6}, sum = 5 + 1 + 6 = 12
{2, 9}, sum = 2 + 9 = 11解決方案方法
在這裡，我們將對問題有一個替代解決方案，該解決方案使用動態規劃方法。在這種方法中，我們將找到滿足給定條件的子序列並列印其中的最大值。我們將建立一個數組 maxSumDP[n]，它儲存建立的子序列的最大子序列和。元素 maxSumDP[i] 儲存透過從索引 i 到 n-1 取元素建立的子序列的最大和。為此，我們可以考慮陣列 arr[i] 的當前元素，即 maxSumDP[i] = arr[i] + maxSumDP[i+2]。或者不考慮陣列 arr[i] 的當前元素，即 maxSumDP[i] = maxSumDP[i+2]。
演算法
初始化 -
maxSumDP[]
步驟 2 -
initialize the values of maxSumDP[n−1] and maxSumDP[n−2]. maxSumDP[n−1] = arr[n−1] and maxSumDP[n−2] = max(arr[n−1], arr[n−2]).
步驟 2 -
loop for i −> n−2 to 0
步驟 1.2 -
initialize the value of maxSumDP[i], maxSumDP[i] = maximum of (arr[i] + maxSumDP[i + 2], maxSumDP[i + 1])
步驟 3 -
Return maxSumDP[0] which is the maximum sum sequence sum.
示例
程式說明我們解決方案的工作原理，
#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSum(int arr[], int n){
int maxSumDP[n];
maxSumDP[n−1] = arr[n−1];
maxSumDP[n−2] = max(arr[n−1], arr[n−2]);
for (int i = n − 2; i >= 0; i−−) {
maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2],
maxSumDP[i + 1]);
}
return maxSumDP[0];
}
int main() {
int arr[] = { 5, 2 , 1, 9, 6 };
int n = sizeof(arr) / sizeof(int);
cout<<"The maximum subsequence sum in such a way that no two consecutive elements of the array is "<<calcMaxSum(arr, n);
return 0;
}輸出
The maximum subsequence sum in such a way that no two consecutive elements of the array is 14
更新於： 2020-12-09
328 次檢視
廣告