1744: Найбільша сума суміжних
Перегляд у форматі PDFДано масив \(A\) з \(N\) цілих чисел.
Знайдіть суміжний підмасив (що містить принаймні одне число), який має максимальну суму.
Формат вхідних даних
Перший рядок вхідного потоку містить ціле число \(N\).
Наступний рядок містить \(N\) цілих чисел \(A_i\)
Числа у рядках розділяються пропуском.
Формат вихідних даних
У вихідний потік вивести максимальну суму.
Обмеження:
- \(1 ≤ N ≤ 10^6\)
- \(-10^7 ≤ A_i ≤ 10^7\)
Приклад вхідних даних
5
1 2 3 -2 5Приклад вихідних даних
9Приклад вхідних даних
4
-1 -2 -3 -4Приклад вихідних даних
-1
Коментарі
Чи не варто збільшити час для Пайтону? Бо алгоритм, що працює за лінійний час, на С++ заходить, а на Пайтоні вилітає в TLE.