Find maximum sum possible equal sum of three stacks

Given three stack of the positive numbers, the task is to find the possible equal maximum sum of the stacks with removal of top elements allowed. Stacks are represented as array, and the first index of the array represent the top element of the stack.

Examples:

```Input : stack1[] = { 3, 10}
stack2[] = { 4, 5 }
stack3[] = { 2, 1 }
Output : 0
Sum can only be equal after removing all elements
from all stacks.
```

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to compare the sum of each stack, if they are not same, remove the top element of the stack having the maximum sum.

Algorithm for solving this problem:

1. Find sum of all elements of in individual stacks.
2. If the sum of all three stacks is same, then this is the maximum sum.
3. Else remove the top element of the stack having the maximum sum among three of stacks. Repeat step 1 and step 2.

The approach works because elements are positive. To make sum equal, we must remove some element from stack having more sum and we can only remove from top.

Below is the implementation of this approach:

C/C++

 `// C++ program to calculate maximum sum with equal  ` `// stack sum. ` `#include ` `using` `namespace` `std; ` ` `  `// Returns maximum possible equal sum of three stacks ` `// with removal of top elements allowed ` `int` `maxSum(``int` `stack1[], ``int` `stack2[], ``int` `stack3[],  ` `                             ``int` `n1, ``int` `n2, ``int` `n3) ` `{ ` `  ``int` `sum1 = 0, sum2 = 0, sum3 = 0; ` `  `  `  ``// Finding the initial sum of stack1. ` `  ``for` `(``int` `i=0; i < n1; i++) ` `      ``sum1 += stack1[i]; ` ` `  `  ``// Finding the initial sum of stack2. ` `  ``for` `(``int` `i=0; i < n2; i++) ` `      ``sum2 += stack2[i]; ` ` `  `  ``// Finding the initial sum of stack3. ` `  ``for` `(``int` `i=0; i < n3; i++) ` `      ``sum3 += stack3[i]; ` ` `  `  ``// As given in question, first element is top ` `  ``// of stack.. ` `  ``int` `top1 =0, top2 = 0, top3 = 0; ` `  ``int` `ans = 0; ` `  ``while` `(1) ` `  ``{ ` `      ``// If any stack is empty ` `      ``if` `(top1 == n1 || top2 == n2 || top3 == n3) ` `         ``return` `0; ` ` `  `      ``// If sum of all three stack are equal. ` `      ``if` `(sum1 == sum2 && sum2 == sum3) ` `         ``return` `sum1; ` `     `  `      ``// Finding the stack with maximum sum and  ` `      ``// removing its top element. ` `      ``if` `(sum1 >= sum2 && sum1 >= sum3) ` `         ``sum1 -= stack1[top1++]; ` `      ``else` `if` `(sum2 >= sum3 && sum2 >= sum3) ` `         ``sum2 -= stack2[top2++]; ` `      ``else` `if` `(sum3 >= sum2 && sum3 >= sum1) ` `         ``sum3 -= stack3[top3++]; ` `   ``} ` `} ` ` `  `// Driven Program ` `int` `main() ` `{ ` `  ``int` `stack1[] = { 3, 2, 1, 1, 1 }; ` `  ``int` `stack2[] = { 4, 3, 2 }; ` `  ``int` `stack3[] = { 1, 1, 4, 1 }; ` ` `  `  ``int` `n1 = ``sizeof``(stack1)/``sizeof``(stack1[0]); ` `  ``int` `n2 = ``sizeof``(stack2)/``sizeof``(stack2[0]); ` `  ``int` `n3 = ``sizeof``(stack3)/``sizeof``(stack3[0]); ` ` `  `  ``cout << maxSum(stack1, stack2, stack3, n1, n2, n3) << endl; ` `  ``return` `0; ` `}  `

Java

 `// JAVA Code for Find maximum sum possible  ` `// equal sum of three stacks ` `class` `GFG { ` `      `  `    ``// Returns maximum possible equal sum of three  ` `    ``// stacks with removal of top elements allowed ` `    ``public` `static` `int` `maxSum(``int` `stack1[], ``int` `stack2[], ` `                            ``int` `stack3[], ``int` `n1, ``int` `n2, ` `                                               ``int` `n3) ` `    ``{ ` `      ``int` `sum1 = ``0``, sum2 = ``0``, sum3 = ``0``; ` `       `  `      ``// Finding the initial sum of stack1. ` `      ``for` `(``int` `i=``0``; i < n1; i++) ` `          ``sum1 += stack1[i]; ` `      `  `      ``// Finding the initial sum of stack2. ` `      ``for` `(``int` `i=``0``; i < n2; i++) ` `          ``sum2 += stack2[i]; ` `      `  `      ``// Finding the initial sum of stack3. ` `      ``for` `(``int` `i=``0``; i < n3; i++) ` `          ``sum3 += stack3[i]; ` `      `  `      ``// As given in question, first element is top ` `      ``// of stack.. ` `      ``int` `top1 =``0``, top2 = ``0``, top3 = ``0``; ` `      ``int` `ans = ``0``; ` `      ``while` `(``true``) ` `      ``{ ` `          ``// If any stack is empty ` `          ``if` `(top1 == n1 || top2 == n2 || top3 == n3) ` `             ``return` `0``; ` `      `  `          ``// If sum of all three stack are equal. ` `          ``if` `(sum1 == sum2 && sum2 == sum3) ` `             ``return` `sum1; ` `          `  `          ``// Finding the stack with maximum sum and  ` `          ``// removing its top element. ` `          ``if` `(sum1 >= sum2 && sum1 >= sum3) ` `             ``sum1 -= stack1[top1++]; ` `          ``else` `if` `(sum2 >= sum3 && sum2 >= sum3) ` `             ``sum2 -= stack2[top2++]; ` `          ``else` `if` `(sum3 >= sum2 && sum3 >= sum1) ` `             ``sum3 -= stack3[top3++]; ` `       ``} ` `    ``} ` `     `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `          ``int` `stack1[] = { ``3``, ``2``, ``1``, ``1``, ``1` `}; ` `          ``int` `stack2[] = { ``4``, ``3``, ``2` `}; ` `          ``int` `stack3[] = { ``1``, ``1``, ``4``, ``1` `}; ` `          `  `          ``int` `n1 = stack1.length; ` `          ``int` `n2 = stack2.length; ` `          ``int` `n3 = stack3.length; ` `          `  `          ``System.out.println(maxSum(stack1, stack2,  ` `                               ``stack3, n1, n2, n3)); ` `    ``} ` `  ``} ` `// This code is contributed by Arnav Kr. Mandal. `

Python

 `# Python program to calculate maximum sum with equal  ` `# stack sum. ` `# Returns maximum possible equal sum of three stacks ` `# with removal of top elements allowed ` `def` `maxSum(stack1, stack2, stack3, n1, n2, n3): ` `    ``sum1, sum2, sum3 ``=` `0``, ``0``, ``0` `   `  `  ``# Finding the initial sum of stack1. ` `    ``for` `i ``in` `range``(n1): ` `        ``sum1 ``+``=` `stack1[i] ` `  `  `  ``# Finding the initial sum of stack2. ` `    ``for` `i ``in` `range``(n2): ` `        ``sum2 ``+``=` `stack2[i] ` `  `  `  ``# Finding the initial sum of stack3. ` `    ``for` `i ``in` `range``(n3): ` `        ``sum3 ``+``=` `stack3[i] ` `  `  `  ``# As given in question, first element is top ` `  ``# of stack.. ` `    ``top1, top2, top3 ``=` `0``, ``0``, ``0` `    ``ans ``=` `0` `    ``while` `(``1``): ` `      ``# If any stack is empty ` `        ``if` `(top1 ``=``=` `n1 ``or` `top2 ``=``=` `n2 ``or` `top3 ``=``=` `n3): ` `            ``return` `0` `  `  `      ``# If sum of all three stack are equal. ` `        ``if` `(sum1 ``=``=` `sum2 ``and` `sum2 ``=``=` `sum3): ` `            ``return` `sum1 ` `      `  `      ``# Finding the stack with maximum sum and  ` `      ``# removing its top element. ` `        ``if` `(sum1 >``=` `sum2 ``and` `sum1 >``=` `sum3): ` `            ``sum1 ``-``=` `stack1[top1] ` `            ``top1``=``top1``+``1` `        ``elif` `(sum2 >``=` `sum3 ``and` `sum2 >``=` `sum3): ` `            ``sum2 ``-``=` `stack2[top2] ` `            ``top2``=``top2``+``1` `        ``elif` `(sum3 >``=` `sum2 ``and` `sum3 >``=` `sum1): ` `            ``sum3 ``-``=` `stack3[top3] ` `            ``top3``=``top3``+``1` `  `  `# Driven Program ` `stack1 ``=` `[ ``3``, ``2``, ``1``, ``1``, ``1` `] ` `stack2 ``=` `[ ``4``, ``3``, ``2` `] ` `stack3 ``=` `[ ``1``, ``1``, ``4``, ``1` `] ` `  `  `n1 ``=` `len``(stack1) ` `n2 ``=` `len``(stack2) ` `n3 ``=` `len``(stack3) ` `  `  `print` `maxSum(stack1, stack2, stack3, n1, n2, n3) ` ` `  `#This code is contributed by Afzal Ansari `

C#

 `// C# Code for Find maximum sum with ` `// equal sum of three stacks ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Returns maximum possible equal  ` `    ``// sum of three stacks with removal  ` `    ``// of top elements allowed ` `    ``public` `static` `int` `maxSum(``int``[] stack1, ` `               ``int``[] stack2, ``int``[] stack3, ` `                   ``int` `n1, ``int` `n2, ``int` `n3) ` `    ``{ ` `         `  `        ``int` `sum1 = 0, sum2 = 0, sum3 = 0; ` ` `  `        ``// Finding the initial sum of  ` `        ``// stack1. ` `        ``for` `(``int` `i = 0; i < n1; i++) ` `            ``sum1 += stack1[i]; ` ` `  `        ``// Finding the initial sum of  ` `        ``// stack2. ` `        ``for` `(``int` `i = 0; i < n2; i++) ` `            ``sum2 += stack2[i]; ` ` `  `        ``// Finding the initial sum of  ` `        ``// stack3. ` `        ``for` `(``int` `i = 0; i < n3; i++) ` `            ``sum3 += stack3[i]; ` ` `  `        ``// As given in question, first  ` `        ``// element is top of stack.. ` `        ``int` `top1 = 0, top2 = 0, top3 = 0; ` ` `  `        ``while` `(``true``) { ` `             `  `            ``// If any stack is empty ` `            ``if` `(top1 == n1 || top2 == n2  ` `                            ``|| top3 == n3) ` `                ``return` `0; ` ` `  `            ``// If sum of all three stack  ` `            ``// are equal. ` `            ``if` `(sum1 == sum2 && sum2 == sum3) ` `                ``return` `sum1; ` ` `  `            ``// Finding the stack with maximum  ` `            ``// sum and removing its top element. ` `            ``if` `(sum1 >= sum2 && sum1 >= sum3) ` `                ``sum1 -= stack1[top1++]; ` `            ``else` `if` `(sum2 >= sum3 && sum2 >= sum3) ` `                ``sum2 -= stack2[top2++]; ` `            ``else` `if` `(sum3 >= sum2 && sum3 >= sum1) ` `                ``sum3 -= stack3[top3++]; ` `        ``} ` `    ``} ` ` `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] stack1 = { 3, 2, 1, 1, 1 }; ` `        ``int``[] stack2 = { 4, 3, 2 }; ` `        ``int``[] stack3 = { 1, 1, 4, 1 }; ` ` `  `        ``int` `n1 = stack1.Length; ` `        ``int` `n2 = stack2.Length; ` `        ``int` `n3 = stack3.Length; ` ` `  `        ``Console.Write(maxSum(stack1, stack2, ` `                        ``stack3, n1, n2, n3)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

PHP

 `= ``\$sum2` `&& ``\$sum1` `>= ``\$sum3``) ` `                ``\$sum1` `-= ``\$stack1``[``\$top1``++]; ` `                 `  `        ``else` `if` `(``\$sum2` `>= ``\$sum3` `&& ``\$sum2` `>=``\$sum3``) ` `                ``\$sum2` `-= ``\$stack2``[``\$top2``++]; ` `                 `  `        ``else` `if` `(``\$sum3` `>= ``\$sum2` `&& ``\$sum3` `>= ``\$sum1``) ` `                ``\$sum3` `-= ``\$stack3``[``\$top3``++]; ` `    ``} ` `} ` ` `  `// Driver Code ` `\$stack1` `= ``array``(3, 2, 1, 1, 1); ` `\$stack2` `= ``array``(4, 3, 2); ` `\$stack3` `= ``array``(1, 1, 4, 1); ` ` `  `\$n1` `= sizeof(``\$stack1``); ` `\$n2` `= sizeof(``\$stack2``); ` `\$n3` `= sizeof(``\$stack3``); ` `echo` `maxSum(``\$stack1``, ``\$stack2``,  ` `            ``\$stack3``, ``\$n1``,  ` `            ``\$n2``, ``\$n3``) ; ` `             `  `// This code is contributed by nitin mittal ` `?> `

Output:

```5
```

Time Complexity : O(n1 + n2 + n3) where n1, n2 and n3 are sizes of three stacks.

tags:

Greedy Stack Greedy Stack