คำชี้แจงปัญหา
รับอาร์เรย์ arr[] ค้นหาค่าสูงสุดของผลรวมคำนำหน้าซึ่งเป็นผลรวมต่อท้ายสำหรับดัชนี i ใน arr[]
ตัวอย่าง
หากอาร์เรย์อินพุตเป็น −
Arr[] ={1, 2, 3, 5, 3, 2, 1} ดังนั้นเอาต์พุตคือ 11 เป็น −
- ผลรวมคำนำหน้า =arr[0..3] =1 + 2 + 3 + 5 =11 และ
- คำต่อท้าย =arr[3..6] =5 + 3 + 2 + 1 =11
อัลกอริทึม
- สำรวจอาร์เรย์และเก็บผลรวมคำนำหน้าสำหรับแต่ละดัชนีในอาร์เรย์ presum[] ซึ่ง presum[i] จะเก็บผลรวมของ subarray arr[0..i]
- สำรวจอาร์เรย์อีกครั้งและเก็บผลรวมต่อท้ายไว้ในคำต่อท้ายอาร์เรย์อื่น[] ซึ่ง suffsum[i] จะเก็บผลรวมของ subarray 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
