C++で3つのスタックの可能な最大合計に等しい合計を見つけます

正の数のスタックが3つあるとします。最上位要素の削除が許可されているスタックの可能な最大合計を見つける必要があります。スタックは配列として表されます。配列の最初のインデックスは、スタックの最上位要素を表します。スタック要素が[3、10]、[4、5]、[2、1]のようであると仮定します。出力は0になります。合計は、すべてのスタックからすべての要素を削除した後にのみ等しくなります。

これを解決するために、私たちはこの考えに従います。アイデアは、各スタックの合計を比較し、それらが等しくない場合は、最大の合計を持つスタックの一番上の要素を削除することです。次の手順に従います-

• 個々のスタック内ののすべての要素の合計を見つけます。

• 3つのスタックすべての合計が等しい場合、これが最大の合計になります。

• それ以外の場合は、3つのスタックの中で合計が最大のスタックの最上位要素を削除します。次に、手順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