คำอธิบายปัญหา
กำหนดอาร์เรย์ arr[] หาค่าสูงสุดของ prefix sum ซึ่งก็คือ suffix sum สำหรับดัชนี i ใน arr[]
ตัวอย่าง
ถ้าอาร์เรย์นำเข้าคือ –
Arr[] = {1, 2, 3, 5, 3, 2, 1} ผลลัพธ์คือ 11 ดังนี้:
- Prefix sum = arr[0..3] = 1 + 2 + 3 + 5 = 11 และ
- Suffix sum = arr[3..6] = 5 + 3 + 2 + 1 = 11
อัลกอริทึม
- เดินทางผ่านอาร์เรย์และเก็บ prefix sum สำหรับแต่ละดัชนีในอาร์เรย์ presum[] โดย presum[i] เก็บผลรวมของซับอาร์เรย์ arr[0..i]
- เดินทางผ่านอาร์เรย์อีกครั้งและเก็บ suffix sum ในอีกอาร์เรย์หนึ่งคือ suffsum[] โดย suffsum[i] เก็บผลรวมของซับอาร์เรย์ arr[i..n-1]
- สำหรับแต่ละดัชนี ตรวจสอบว่า presum[i] เท่ากับ suffsum[i] หรือไม่ และถ้าเท่ากัน ให้เปรียบเทียบค่านั้นกับค่าสูงสุดรวมจนถึงตอนนั้น
ตัวอย่างโค้ด
#include <bits/stdc++.h> using namespace std; int getMaxSum(int *arr, int n) { int preSum[n]; int suffSum[n]; int result = INT_MIN; preSum[0] = arr[0]; for (int i = 1; i < n; ++i) { preSum[i] = preSum[i - 1] + arr[i]; } suffSum[n - 1] = arr[n - 1]; if (preSum[n - 1] == suffSum[n - 1]) { result = max(result, preSum[n - 1]); } for (int i = n - 2; i >= 0; --i) { suffSum[i] = suffSum[i + 1] + arr[i]; if (suffSum[i] == preSum[i]) { result = max(result, preSum[i]); } } return result; } int main() { int arr[] = {1, 2, 3, 5, 3, 2, 1}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Max equlibrium sum = " << getMaxSum(arr, n) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้:
Max equlibrium sum = 11
