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ẽ giống nhau. Giả sử mảng A = [2, 3, 4, 1, 4, 5], Kết quả là 1, vì vậy các mảng con trước 1 và sau 1 được lấy. [2, 3, 4], và [4, 5].
Để giải quyết bài toán này, chúng ta sẽ tính tổng toàn bộ mảng trừ phần tử đầu tiên vào right_sum. Coi đó là phần tử phân chia. Chúng ta sẽ duyệt từ trái sang phải. Trừ một phần tử từ right_sum và cộng một phần tử vào left_sum, chúng ta lấy đ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); }
Kết quả
Partition element: 1