1744: Найбільша сума суміжних

Переглянути як PDF
Надіслати розвʼязок
Бали: 20,00 (частково)
Ліміт часу: 1.0s
Ліміт памʼяті: 64M
Автор:
zvit
Тип задачі
Дозволені мови
Assembly, Awk, Brain****, C, C++, Java, mono C#, Pascal, Perl, Python, Sed, Text, vb

Дано масив ~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

Коментарі

Будь ласка, прочитайте правила перед коментуванням.


  • 0
    Javdet  прокоментовано 8 Березень 2024, 12:11

    Чи не варто збільшити час для Пайтону? Бо алгоритм, що працює за лінійний час, на С++ заходить, а на Пайтоні вилітає в TLE.