ধরুন ধনাত্মক সংখ্যার তিনটি স্ট্যাক আছে। প্রতিটি স্ট্যাকের উপরের উপাদানগুলো সরিয়ে তিনটি স্ট্যাকের যোগফল সমান করার চেষ্টা করनी होगी। স্ট্যাকগুলো অ্যারে আকারে দেওয়া থাকবে, যেখানে প্রথম ইনডেক্সটি স্ট্যাকের টপ উপাদান। উদাহরণস্বরূপ, স্ট্যাকগুলো [3, 10], [4, 5] এবং [2, 1] হলে আউটপুট হবে ০, কারণ সব উপাদান সরিয়ে ফেললেই যোগফল সমান হয়।
- প্রতিটি স্ট্যাকের সব উপাদানের যোগফল বের করুন।
- যদি তিনটি স্ট্যাকের যোগফল সমান হয়, তবে সেটিই সর্বোচ্চ যোগফল।
- অন্যথায়, যেটির যোগফল সর্বাধিক, সেটির টপ উপাদানটি সরিয়ে ফেলুন। ধাপ ১ এবং ২ পুনরাবৃত্তি করুন।
#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 >= add1) 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
