ধরুন আমাদের কাছে ধনাত্মক সংখ্যার তিনটি স্ট্যাক আছে। আমাদের অনুমোদিত শীর্ষ উপাদান অপসারণের সাথে স্ট্যাকের সম্ভাব্য সমান সর্বোচ্চ যোগফল খুঁজে বের করতে হবে। স্ট্যাকগুলি একটি অ্যারে হিসাবে উপস্থাপিত হয়। অ্যারের প্রথম সূচকটি স্ট্যাকের শীর্ষ উপাদানকে উপস্থাপন করে। ধরুন স্ট্যাকের উপাদানগুলো হল [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
