我们拿到了三个分别包含正整数的栈 s1、s2 和 s3。现在的任务是：通过从栈顶移除元素，使这三个栈中剩余元素的和相等，并且我们需要找出这个可能的最大相等和。我们可以从任意栈的顶部移除元素，但最终必须保证所有三个栈的剩余元素之和完全一致。我们的目标是确定经过一系列移除操作后，这三个栈所能达到的最大相等和。
注意： 在实际代码表示中，栈通常用数组来表示，其中数组的第一个索引（即下标 0）对应栈顶元素。
示例：
> 输入： s1 = [3, 2, 1, 1, 1], s2 = [4, 3, 2], s3 = [2, 5, 4, 1]
> 输出： 5
> 解释： 我们可以从第 1 个栈弹出 2 个元素，从第 2 个栈弹出 1 个元素，并从第 3 个栈弹出 2 个元素。
> !Find-maximum-sum-possible-equal-sum-of-three-stacks-2
> 输入： s1 = [3, 10]
> s2 = [4, 5]
> s3 = [2, 1]
> 输出： 0
> 解释： 只有当所有栈中的所有元素都被移除后，它们的和才能相等（均为 0）。
贪心算法 – 时间复杂度 O(n1 + n2 + n3)，空间复杂度 O(1)
> 这个思路的核心在于比较每个栈当前的总和。如果它们的和不相等，我们就移除当前总和最大的那个栈的栈顶元素。
>
> 解决该问题的具体算法步骤如下：
>
> 1. 分别计算这三个栈中所有元素的总和。
> 2. 如果三个栈的总和相等，那么这就是我们要求的最大相等和。
> 3. 否则，找出三个栈中总和最大的那个栈，移除它的栈顶元素（即从总和中减去该元素值，并将栈顶指针下移）。然后重复步骤 1 和步骤 2。
>
> 这种方法是可行的，因为题目中给出的元素都是正整数。为了使和相等，我们必须从总和较大的栈中移除一些元素，而我们只能从栈顶进行移除操作。
C++
CODEBLOCK_1f88a961
CODEBLOCK_328fc74ajava
import java.util.List;
import java.util.ArrayList;
public class GfG {
public static int maxSum(List s1, List s2, List s3) {
int sum1 = 0, sum2 = 0, sum3 = 0;
// 手动计算 s1 的元素总和
for (int i = 0; i < s1.size(); i++) {
sum1 += s1.get(i);
}
// 手动计算 s2 的元素总和
for (int i = 0; i < s2.size(); i++) {
sum2 += s2.get(i);
}
// 手动计算 s3 的元素总和
for (int i = 0; i = sum2 && sum1 >= sum3)
sum1 -= s1.get(top1++);
else if (sum2 >= sum1 && sum2 >= sum3)
sum2 -= s2.get(top2++);
else
sum3 -= s3.get(top3++);
}
}
public static void main(String[] args) {
List s1 = new ArrayList();
s1.add(3);
s1.add(2);
s1.add(1);
s1.add(1);
s1.add(1);
List s2 = new ArrayList();
s2.add(4);
s2.add(3);
s2.add(2);
List s3 = new ArrayList();
s3.add(1);
s3.add(1);
s3.add(4);
s3.add(1);
System.out.println(maxSum(s1, s2, s3));
}
}
CODEBLOCK_7fc2debb
Python
def max_sum(s1, s2, s3):
sum1 = sum(s1)
sum2 = sum(s2)
sum3 = sum(s3)
top1 = top2 = top3 = 0
while True:
# 如果任意一个栈被完全移空，则无法达到相等和，返回 0
if top1 == len(s1) or top2 == len(s2) or top3 == len(s3):
return 0
# 如果三个栈的和相等，则找到了最大相等和
if sum1 == sum2 and sum2 == sum3:
return sum1
# 移除当前总和最大的栈的顶部元素
if sum1 >= sum2 and sum1 >= sum3:
sum1 -= s1[top1]
top1 += 1
elif sum2 >= sum1 and sum2 >= sum3:
sum2 -= s2[top2]
top2 += 1
else:
sum3 -= s3[top3]
top3 += 1
“`