|
Максимальное произведение
(Время: 1 сек. Память: 64 Мб Сложность: 23%)
Задан массив натуральных чисел [a1, a2, ... , an]. Весом массива назовём сумму его элементов.
Необходимо разрезать заданный массив на два непустых массива [a1, a2, ... , ai] и [ai+1, ai+2, ... , an] так, чтобы произведение их весов было как можно больше.
Требуется написать программу, которая по заданному массиву определяет, после какого элемента
его необходимо разрезать, чтобы произведение весов получившихся массивов было максимальным.
Входные данные
В первой строке входного файла INPUT.TXT находится целое число n — количество элементов в массиве
(2 ≤ n ≤ 2×105). В следующей строке находятся n целых чисел a1, a2, ... , an — элементы массива (1 ≤ ai ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число — номер элемента, после которого необходимо разрезать заданный массив.
Если оптимальных вариантов ответа несколько, можно вывести любой из них.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 2 3 | 2 |
Пояснение к примеру
Если сделать разрез после первого элемента, произведение весов равно 1×(2+3) = 5, а если
после второго, то (1+2)×3 = 9.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
