Tổng cân bằng lớn nhất trong mảng trong C++

Đề bài

Cho mảng arr[]. Tìm giá trị lớn nhất của tổng tiền tố (prefix sum) cũng là tổng hậu tố (suffix sum) tại chỉ số i.

Ví dụ

Mảng: {1, 2, 3, 5, 3, 2, 1} → Kết quả = 11 vì:

• Prefix sum = arr[0..3] = 1 + 2 + 3 + 5 = 11
• Suffix sum = arr[3..6] = 5 + 3 + 2 + 1 = 11

Thuật toán

1. Duyệt mảng, lưu prefix sum tại mỗi chỉ số vào mảng preSum[]
2. Duyệt ngược, lưu suffix sum vào mảng suffSum[]
3. Với mỗi chỉ số, nếu preSum[i] == suffSum[i] thì so sánh với max hiện tại

Chương trình C++

#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 equilibrium sum = " << getMaxSum(arr, n) << endl;
    return 0;
}

Kết quả

Max equilibrium sum = 11

Độ phức tạp

• Thời gian: O(n)
• Không gian: O(n) (có thể tối ưu O(1) bằng cách tính suffix sum ngược và so sánh ngay)