1. Идея

Нужно разрезать массив ровно между двумя соседними элементами так, чтобы слева и справа остались непустые части, и абсолютная разность их сумм была минимальной.

Если для некоторого разреза известна сумма левой части pref, а сумма всех элементов равна total, то сумма правой части равна total - pref.

Тогда разность для такого разреза равна abs(pref - (total - pref)).

Значит, задача сводится к тому, чтобы перебрать все возможные места разреза, поддерживать сумму левой части и выбирать минимальное значение этой формулы.

2. Наблюдения

1. Разрез можно сделать только после элементов с индексами от 0 до n - 2, потому что обе части должны быть непустыми.

2. Если каждый раз заново считать суммы левой и правой части, получится слишком медленно: до O(n^2).

3. Но сумму левой части можно накапливать постепенно:

   • сначала pref = 0,
   • добавляем очередной элемент a[i],
   • получаем сумму левой части после разреза за этим элементом.

4. Сумма правой части тогда находится сразу:

   • suf = total - pref.

5. В ответе может быть большое число, поэтому нужен 64-битный тип:

   • в C++ это long long,
   • в Python целые числа уже длинные.

3. Алгоритм

1. Считать n и массив a.
2. Посчитать сумму всех элементов total.
3. Завести:
   • pref = 0 — текущая сумма левой части,
   • ans — минимальная найденная разность.
4. Для каждого i от 0 до n - 2:
   • прибавить a[i] к pref,
   • вычислить suf = total - pref,
   • вычислить diff = abs(pref - suf),
   • обновить ans, если diff меньше.
5. Вывести ans.

4. Почему это работает

Рассмотрим любой допустимый разрез. Он находится между некоторыми соседними элементами, то есть после позиции i, где 0 <= i < n - 1.

Тогда:

• левая часть состоит из элементов a[0], a[1], ..., a[i],
• правая часть состоит из элементов a[i+1], ..., a[n-1].

В цикле алгоритм как раз последовательно рассматривает все такие i.

После добавления a[i] в pref переменная pref становится суммой всех элементов слева от разреза. Так как total — сумма всего массива, сумма правой части равна total - pref.

Значит, для каждого возможного разреза алгоритм точно вычисляет его абсолютную разность сумм.

Так как алгоритм перебирает все допустимые разрезы и для каждого считает правильную разность, а затем выбирает минимум, итоговый ответ и есть минимально возможная абсолютная разность.

5. Сложность

• Подсчёт общей суммы: O(n)
• Перебор всех разрезов: O(n)

Итоговая сложность: O(n)

Дополнительная память:

• O(n) на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    long long total = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        total += a[i];
    }

    long long pref = 0;
    long long ans = -1;

    for (int i = 0; i < n - 1; i++) {
        pref += a[i];
        long long suf = total - pref;
        long long diff = llabs(pref - suf);
        if (ans == -1 || diff < ans) {
            ans = diff;
        }
    }

    cout << ans << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

total = sum(a)
pref = 0
ans = None

for i in range(n - 1):
    pref += a[i]
    suf = total - pref
    diff = abs(pref - suf)
    if ans is None or diff < ans:
        ans = diff

print(ans)