इस समस्या में, हमें 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