Задача 5. Максимальное произведение ≡

Условие

Задан массив натуральных чисел [a₁, a₂, …, a_n]. Весом массива назовём сумму его элементов.

Необходимо разрезать заданный массив на два непустых массива [a₁, a₂, …, a_i] и [a_i + 1, a_i + 2, …, a_n] так, чтобы произведение их весов было как можно больше.

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

Формат входных данных

В первой строке входных данных находится целое число n — количество элементов в массиве (2 ≤ n ≤ 2 ⋅ 10⁵). В следующей строке находятся n целых чисел a₁, a₂, …, a_n — элементы массива (1 ≤ a_i ≤ 10⁹).

Формат выходных данных

Выведите одно число — номер элемента, после которого необходимо разрезать заданный массив. Если оптимальных вариантов ответа несколько, можно вывести любой из них.

Ограничения

1 ≤ a_i ≤ 10⁹

2 ≤ n ≤ 2 ⋅ 10⁵

Система оценивания

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

Замечание

Если сделать разрез после первого элемента, произведение весов равно 1 ⋅ (2 + 3) = 5, а если после второго, то (1 + 2) ⋅ 3 = 9

Примеры тестов

3
1 2 3

2

Разбор

В первой подзадаче можно просто перебрать все возможные точки разреза, для каждой найти сумму элементов, перемножить и выбрать оптимальное значение. При этом сумму можно каждый раз вычислять заново, получив время работы O(n2). Благодаря тому, что сумма элементов всего массива не превышает 10⁹, все действия можно безопасно выполнить в 64-битном типе данных. Для решения четвертой подзадачи можно заметить, что вместо суммирования элементов заново, каждый раз при перемещении границы вправо на один элемент можно пересчитывать сумму за O(1). Следовательно решение работает за O(n).

Для решения остальных подзадач метод просуммировать элементы и перемножить не подходит произведение получается слишком большое и не влезает в 64-битный тип данных. Заметим, что решения на языке Python или в случае доступности 128-битного типа данных, в принципе, лишены этого недостатка. Но есть решение, которое не выполняет операций умножения.

Решим сначала подзадачи, где все значения равны. Пусть массив поделен на части размера k и l. Заметим, что произведение равно (k ⋅ a) ⋅ (l ⋅ a), где a — значение элементов массива, а k + l = n. Так как (k ⋅ a) ⋅ (l ⋅ a) = (k ⋅ l) ⋅ a² = k ⋅ (n − k) ⋅ a², достаточно максимизировать величину k ⋅ (n − k). Эта величина максимальна, когда k примерно равно n / 2, а именно равно n / 2 при чётном n и (n±1) / 2 при нечётном n. Таким образом получаем решение за O(1): вывести ⌊n / 2⌋. Это решение подходит для второй и пятой подзадачи, также можно не находить математически максимум k ⋅ (n − k), а перебрать значения k. Во второй подзадаче для вычисления k ⋅ (n − k) при этом достаточно 32-битного типа данных.

Наконец, для решения на полный балл заметим, что идея, что значение k ⋅ (n − k) максимально при k в районе n / 2 обобщается следующим образом. Пусть s — сумма всех элементов массива, а t_k — сумма первых k элементов. Тогда произведение t_k ⋅ (s − t_k) максимально, когда tk максимально близко к s / 2. Можно перебирать k и вычислять t_k за O(n) в первых трёх подзадачах, либо вычислять t_k за O(1) с помощью префиксных сумм, или пересчитывать за O(1) при увеличении k на 1, получая полное решение.