หาผลรวมสูงสุดที่เท่ากันของสามสแต็กใน C++

ปัญหา

กำหนดให้มีสามสแต็กของจำนวนเต็มบวก จงหาผลรวมสูงสุดที่เท่ากันของทั้งสามสแต็ก โดยอนุญาตให้เอาองค์ประกอบด้านบน (top) ออกได้ สแต็กถูกแทนด้วยอาร์เรย์ โดยดัชนีแรกคือองค์ประกอบด้านบน

ตัวอย่าง: สแต็ก [3, 10], [4, 5], [2, 1] ผลลัพธ์คือ 0 เพราะต้องเอาออกหมดถึงจะเท่ากัน

อัลกอริทึม

1. คำนวณผลรวมของแต่ละสแต็ก
2. ถ้าผลรวมของทั้งสามเท่ากันแล้ว นั่นคือคำตอบ
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 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 << "The maximum sum is: " << maxStackSum(stack1, stack2, stack3, size1, size2, size3);
}

ผลลัพธ์

The maximum sum is: 5