Tuyên bố vấn đề
Cho một mảng arr []. Tìm giá trị lớn nhất của tổng tiền tố cũng là tổng hậu tố cho chỉ mục i trong arr [].
Ví dụ
Nếu mảng đầu vào là -
Arr [] ={1, 2, 3, 5, 3, 2, 1} thì đầu ra là 11 as -
- Tiền tố sum =arr [0..3] =1 + 2 + 3 + 5 =11 và
- Tổng hậu tố =arr [3..6] =5 + 3 + 2 + 1 =11
Thuật toán
- Duyệt qua mảng và lưu trữ tổng tiền tố cho mỗi chỉ mục trong mảng presum [], trong đó presum [i] lưu trữ tổng của mảng con arr [0..i]
- Đảo ngược mảng một lần nữa và lưu trữ tổng hậu tố trong một mảng khác với hậu tố [], trong đó hậu tố [i] lưu trữ tổng của mảng con arr [i..n-1]
- Đối với mỗi chỉ mục, hãy kiểm tra xem giá trị đặt trước [i] có bằng với giá trị đủ [i] hay không và nếu chúng bằng nhau thì hãy so sánh, có giá trị với giá trị tối đa tổng thể cho đến nay
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Max equlibrium sum = 11