สมมติว่าเรามีอาร์เรย์ A มี n สมาชิก ภารกิจของเราคือแบ่งอาร์เรย์ A เป็นสองซับอาร์เรย์ (Subarrays) ที่ผลรวมของแต่ละซับอาร์เรย์จะเท่ากัน สมมติอาร์เรย์ A = [2, 3, 4, 1, 4, 5] ผลลัพธ์คือ 1 ดังนั้นซับอาร์เรย์ก่อน 1 และหลัง 1 ถูกนำมาใช้ [2, 3, 4] และ [4, 5]
เพื่อแก้ปัญหานี้ เราจะคำนวณผลรวมของอาร์เรย์ทั้งหมดยกเว้นสมาชิกแรกใน right_sum ถือว่านั้นคือสมาชิกแบ่งพื้นที่ (Partition Element) เราจะท่องจากซ้ายไปขวา ลบสมาชิกออกจาก 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
