Giả sử chúng ta có một mảng A, nó có n phần tử. Nhiệm vụ của chúng ta là chia mảng A thành hai mảng con, sao cho tổng của mỗi mảng con sẽ bằng nhau. Giả sử mảng A =[2, 3, 4, 1, 4, 5], đầu ra là 1, do đó các mảng con trước 1 và sau 1 được lấy. [2, 3, 4] và [4, 5].
Để giải quyết vấn đề này, chúng ta sẽ tính toán toàn bộ mảng ngoại trừ phần tử đầu tiên trong right_sum. Hãy coi đó là phần tử phân vùng. Chúng ta sẽ đi từ trái sang phải. Trừ một phần tử khỏi right_sum và thêm một phần tử vào left_sum, chúng ta đạt được điểm khi right_sum =left_sum.
Ví dụ
#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);
} Đầu ra
Partition element: 1