इस समस्या में, हमें n धनात्मक पूर्णांकों से युक्त एक सरणी arr[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो अधिकतम उपअनुक्रम योग ढूंढे जैसे कि कोई तीन लगातार न हों।
समस्या विवरण
यहां, हमें सरणी से बने अनुक्रमों का योग ढूंढना है जैसे कि कोई तीन लगातार तत्व न हों।
सरणी के लगातार तत्व वे तत्व हैं जो सूचकांक के समान क्रम का पालन करते हैं।
arr[0], arr[1], arr[2], …
उदाहरण
इनपुट
arr[] = {5, 9, 12, 15}
आउटपुट
32
व्याख्या
योग = 5 + 12 + 15 = 32
समाधान दृष्टिकोण
समस्या का एक सरल समाधान वर्तमान सूचकांक तक के योग को संग्रहीत करने के लिए एक सहायक सरणी बनाना है। और फिर योग ढूंढना और लगातार योगों की जांच करके सूचकांक तक के योग की जांच करना।
पहले दो योग मानों के लिए, 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
