मान लीजिए कि हमारे पास सकारात्मक संख्याओं के तीन ढेर हैं। हमें अनुमत शीर्ष तत्वों को हटाने के साथ स्टैक के संभावित समान अधिकतम योग को खोजना होगा। ढेर को एक सरणी के रूप में दर्शाया जाता है। सरणी का पहला सूचकांक स्टैक के शीर्ष तत्व का प्रतिनिधित्व करता है। मान लीजिए कि स्टैक तत्व [3, 10], [4, 5] और [2, 1] जैसे हैं। आउटपुट 0 होगा। सभी तत्वों को सभी स्टैक से हटाने के बाद ही योग बराबर हो सकता है।
इसे हल करने के लिए, हम इस विचार का पालन करेंगे। विचार प्रत्येक स्टैक के योग की तुलना करना है, यदि वे समान नहीं हैं, तो अधिकतम योग वाले स्टैक के शीर्ष तत्व को हटा दें। हम इन चरणों का पालन करेंगे -
-
अलग-अलग स्टैक में सभी तत्वों का योग ज्ञात करें।
-
यदि तीनों ढेरों का योग बराबर है, तो यह अधिकतम योग है।
-
अन्यथा स्टैक के शीर्ष तत्व को हटा दें जिसमें तीन स्टैक के बीच अधिकतम योग हो। फिर चरण 1 और चरण 2 दोहराएं।
उदाहरण
#include <iostream>
#include <algorithm>
using namespace std;
int maxStackSum(int stk1[], int stk2[], int stk3[], int size1, int size2, int size3) {
int add1 = 0, add2 = 0, add3 = 0;
for (int i=0; i < size1; i++)
add1 += stk1[i];
for (int i=0; i < size2; i++)
add2 += stk2[i];
for (int i=0; i < size3; i++)
add3 += stk3[i];
int top1 =0, top2 = 0, top3 = 0;
int ans = 0;
while (true){
if (top1 == size1 || top2 == size2 || top3 == size3)
return 0;
if (add1 == add2 && add2 == add3)
return add1;
if (add1 >= add2 && add1 >= add3)
add1 -= stk1[top1++];
else if (add2 >= add3 && add2 >= add3)
add2 -= stk2[top2++];
else if (add3 >= add2 && add3 >= add1)
add3 -= stk3[top3++];
}
}
int main() {
int stack1[] = { 3, 2, 1, 1, 1 };
int stack2[] = { 4, 3, 2 };
int stack3[] = { 1, 1, 4, 1 };
int size1 = sizeof(stack1)/sizeof(stack1[0]);
int size2 = sizeof(stack2)/sizeof(stack2[0]);
int size3 = sizeof(stack3)/sizeof(stack3[0]);
cout << "The maximum sum is: " << maxStackSum(stack1, stack2, stack3, size1, size2, size3);
} आउटपुट
The maximum sum is: 5