Giả sử chúng ta có ba ngăn xếp số dương. Chúng ta phải tìm tổng số ngăn xếp tối đa bằng nhau có thể có với việc loại bỏ các phần tử trên cùng được phép. Các ngăn xếp được biểu diễn dưới dạng một mảng. Chỉ mục đầu tiên của mảng đại diện cho phần tử trên cùng của ngăn xếp. Giả sử các phần tử ngăn xếp giống như [3, 10], [4, 5] và [2, 1]. Đầu ra sẽ là 0. Tổng chỉ có thể bằng nhau sau khi loại bỏ tất cả các phần tử khỏi tất cả các ngăn xếp.
Để giải quyết điều này, chúng tôi sẽ làm theo ý tưởng này. Ý tưởng là so sánh tổng của mỗi ngăn xếp, nếu chúng không bằng nhau, thì loại bỏ phần tử trên cùng của ngăn xếp có tổng lớn nhất. Chúng tôi sẽ làm theo các bước sau -
-
Tìm tổng tất cả các phần tử của từng ngăn xếp.
-
Nếu tổng của cả ba ngăn xếp bằng nhau thì đây là tổng lớn nhất.
-
Nếu không, hãy xóa phần tử trên cùng của ngăn xếp có tổng lớn nhất trong số ba ngăn xếp. Sau đó lặp lại bước 1 và bước 2.
Ví dụ
#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);
} Đầu ra
The maximum sum is: 5