Сумма двух подмножеств как можно ближе

Question

Майк нашел длинную ленту в своем доме.Он приступил к написанию некоторой последовательности целых чисел.Теперь он хотел бы разрезать ленту таким образом, чтобы разница между суммой целых чисел в одной части и в другой была как можно ближе к нулю (в одной части должно быть хотя бы одно число).Вы должны напечатать абсолютное значение этой разности.

Ввод: n (2 ≤ n ≤ 10 ⁶ ), означающий количество чисел, записанных на ленте, а затем n целых чиселa _i (-10 ³ ≤ a ₁ ≤ 10 ³ ) как числа, записанные на ленте.

Вывод: одно целое число, являющееся минимальным абсолютным значением разности между двумя частями.

Пример:
6
1 2 3 4 5 6
Должно вывести:
1

У меня такое ощущение, что я где-то читал такую ​​проблему раньше ... Хотя я не знаю, как ее решить.Я имею в виду, у меня есть подсказка, но я не знаю, правильно ли это.Должен ли я сначала вычислить сумму всей ленты, а затем вычислить слева направо, пока я не окажусь настолько близко к той части, которая будет половиной всей ленты, насколько это возможно?Я имею в виду: я суммирую числа слева направо, постоянно проверяя, превысил ли я половину всего набора.Если сумма подмножества равна половине - мы печатаем ноль.Если точная половина невозможна, мы проверяем ближайшую снизу и сверху и выводим ближайшую.Это нормально?

Answer 1

Начните с одного конца ленты и рассчитайте сумму. Запишите сумму (сумма до этого числа), как вы идете. Теперь проблема заключается в простой задаче поиска, где мы можем искать в подсумах ту, которая ближе всего к общей сумме, деленной на два, используя, например, двоичный поиск .