資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式中最大子序列和，且子序列中不存在三個連續元素
在這個問題中，我們給定一個包含n個正整數的陣列arr[]。我們的任務是建立一個程式來查詢最大子序列和，條件是子序列中不存在三個連續的元素。
問題描述 − 在這裡，我們需要找到從陣列中建立的序列的總和，條件是序列中不存在三個連續的元素。
陣列的連續元素是指按照相同索引順序排列的元素。
arr[0], arr[1], arr[2], …
讓我們舉個例子來理解這個問題，
輸入
arr[] = {5, 9, 12, 15}輸出
32
解釋
Sum = 5 + 12 + 15 = 32
解決方案方法
解決這個問題的一個簡單方法是建立一個輔助陣列來儲存直到當前索引的總和。然後找到總和並透過檢查連續的總和來檢查直到索引的總和。
For the first two sum values, sumVal[0] = arr[0] sumVal[1] = arr[0] + arr[1]
然後，第三個要考慮的值不能直接考慮。為了考慮總和，我們將檢查當前三個元素的條件，如果考慮arr[i]，會增加總和值，則排除arr[i−1]或arr[i−2]。否則不考慮arr[i]，總和保持不變。
sum[i] = max(sum[i−3] + arr[i−1] + arr[i], sum[i−2] + arr[i], sum[i−1])
示例
程式演示了我們解決方案的實現，
#include <iostream>
using namespace std;
int findMaxSubSeqSum(int arr[], int n) {
int maxSumArr[n];
maxSumArr[0] = arr[0];
maxSumArr[1] = arr[0] + arr[1];
maxSumArr[2] = max(maxSumArr[1], max(arr[1] + arr[2], arr[0] +
arr[2]));
for (int i = 3; i < n; i++){
int sum1 = maxSumArr[i − 2] + arr[i];
int sum2 = arr[i] + arr[i − 1] + maxSumArr[i − 3];
maxSumArr[i] = max(max(maxSumArr[i − 1], sum1), sum2);
}
return maxSumArr[n − 1];
}
int main() {
int arr[] = { 5, 9, 12, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum subsequence sum such that no three are
consecutive is "<<findMaxSubSeqSum(arr, n);
return 0;
}輸出
The maximum subsequence sum such that no three are consecutive is 32
更新於: 2020年12月9日
117 次檢視
廣告