Первая олимпиада Олмат.Программирование. 23.02.26

Тема: Искусственный интеллект Уровень: Профи

📜 Первая находка

Вы расшифровали фрагмент кода древней нейросети, найденной в архиве забытого edge-устройства. Это устройство работало автономно — без облака, без постоянного питания, без возможности активировать всю модель целиком.

В логах сохранилось лишь одно правило:

«Активировать можно только непрерывный участок нейронного слоя».

Почему? Ограничения энергии. Перегрев. Ограничения памяти.

Но главная цель системы была ясна — максимально увеличить точность распознавания сигнала, используя лишь часть сети.

Теперь вам предстоит восстановить этот алгоритм.

🧠 Немного о технологии

Edge-устройства — это вычислительные системы, работающие локально: в дронах, автономных сенсорах, медицинских приборах, роботах. Они не могут позволить себе запускать всю нейронную сеть целиком.

Каждый нейрон в слое даёт вклад в итоговую точность модели:

• положительный вклад — улучшает результат,
• отрицательный вклад — создаёт шум или ошибку.

Иногда отдельные нейроны дают резкие отклонения — выбросы.

📌 Вклады нейронов

Вклад нейрона — это числовая величина, отражающая изменение качества модели при его активации.

Выбросы — это элементы массива, резко отличающиеся по значению:

• сильно отрицательные — могут «сломать» хороший участок,
• сильно положительные — могут компенсировать соседние ошибки.

В инженерной практике такие выбросы могут появляться:

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

При активации нейронов важно учитывать:

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

⚙️ Алгоритм как применяется на практике

На практике подобная задача решается линейным алгоритмом оптимизации — поиском максимальной суммы непрерывного подмассива.

Это классическая задача анализа сигналов:

• поиск наиболее "энергетически выгодного" участка сигнала,
• выделение фрагмента с максимальным вкладом,
• фильтрация шума.

📌 Задача

Дан массив целых чисел — вкладов нейронов в точность модели.

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

Вывести максимальную возможную сумму.

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

Первая строка содержит целое число n — количество нейронов. Вторая строка содержит n целых чисел — вклад каждого нейрона.

Ограничения

• 1 ≤ n ≤ 2⋅10⁵
• -10⁹ ≤ aᵢ ≤ 10⁹

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

Выведите одно целое число — максимальную сумму непрерывного подмассива.

📘 Примеры

Пример 1

Входные данные:

9
-2 1 -3 4 -1 2 1 -5 4

Выходные данные:

6

Пояснение: оптимальный блок — [4, -1, 2, 1].

Пример 2

Входные данные:

5
-5 -2 -3 -4 -1

Выходные данные:

-1

Пример 3

Входные данные:

6
3 -2 5 -1 6 -3

Выходные данные:

11

Пояснение: оптимальный блок — [3, -2, 5, -1, 6].