สมมติว่าเรามีอาร์เรย์ A มีองค์ประกอบ n หน้าที่ของเราคือแบ่งอาร์เรย์ A ออกเป็นสองอาร์เรย์ย่อย เพื่อให้ผลรวมของแต่ละอาร์เรย์ย่อยเท่ากัน สมมติว่าอาร์เรย์ A =[2, 3, 4, 1, 4, 5] เอาต์พุตคือ 1 ดังนั้นอาร์เรย์ย่อยก่อน 1 และหลัง 1 จะถูกนำมา [2, 3, 4], และ [4, 5].
เพื่อแก้ปัญหานี้ เราจะคำนวณทั้งอาร์เรย์ ยกเว้นองค์ประกอบแรกใน right_sum พิจารณาว่าเป็นองค์ประกอบการแบ่งพาร์ติชัน เราจะข้ามจากซ้ายไปขวา การลบองค์ประกอบออกจาก right_sum และเพิ่มองค์ประกอบใน left_sum เราจะใช้จุดที่ right_sum =left_sum
ตัวอย่าง
#include<iostream>
using namespace std;
int getPartitionElement(int arr[], int size) {
int right = 0, left = 0;
for (int i = 1; i < size; i++)
right += arr[i];
for (int i = 0, j = 1; j < size; i++, j++) {
right -= arr[j];
left += arr[i];
if (left == right)
return arr[i + 1];
}
return -1;
}
int main() {
int arr[] = { 2, 3, 4, 1, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Partition element: " << getPartitionElement(arr, size);
} ผลลัพธ์
Partition element: 1
