Tìm tổng bằng nhau lớn nhất của ba ngăn xếp trong C++

Cho ba ngăn xếp chứa các số nguyên dương. Nhiệm vụ là tìm tổng bằng nhau lớn nhất có thể đạt được bằng cách loại bỏ các phần tử ở đỉnh ngăn xếp. Các ngăn xếp được biểu diễn dưới dạng mảng, trong đó chỉ số 0 là phần tử đỉnh. Ví dụ: với các ngăn xếp [3, 10], [4, 5] và [2, 1], kết quả là 0 vì chỉ khi loại bỏ hết tất cả phần tử thì tổng mới bằng nhau.

Ý tưởng giải quyết

So sánh tổng của ba ngăn xếp. Nếu chưa bằng nhau, loại bỏ phần tử đỉnh của ngăn xếp có tổng lớn nhất. Lặp lại cho đến khi ba tổng bằng nhau hoặc một ngăn xếp rỗng.

1. Tính tổng các phần tử của từng ngăn xếp.
2. Nếu ba tổng bằng nhau, đó là kết quả.
3. Ngược lại, loại bỏ phần tử đỉnh của ngăn xếp có tổng lớn nhất. Quay lại bước 1.

Ví dụ minh họa

#include <iostream>
#include <algorithm>
using namespace std;

int maxStackSum(int stk1[], int stk2[], int stk3[], int size1, int size2, int size3) {
    int sum1 = 0, sum2 = 0, sum3 = 0;
    
    for (int i = 0; i < size1; i++) sum1 += stk1[i];
    for (int i = 0; i < size2; i++) sum2 += stk2[i];
    for (int i = 0; i < size3; i++) sum3 += stk3[i];
    
    int top1 = 0, top2 = 0, top3 = 0;
    
    while (true) {
        if (top1 == size1 || top2 == size2 || top3 == size3)
            return 0;
        
        if (sum1 == sum2 && sum2 == sum3)
            return sum1;
        
        if (sum1 >= sum2 && sum1 >= sum3)
            sum1 -= stk1[top1++];
        else if (sum2 >= sum3 && sum2 >= sum1)
            sum2 -= stk2[top2++];
        else
            sum3 -= 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 << "Tổng lớn nhất bằng nhau: " << maxStackSum(stack1, stack2, stack3, size1, size2, size3);
    return 0;
}

Kết quả

Tổng lớn nhất bằng nhau: 5