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

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 20,00 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
zvit
Problem type
Allowed languages
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

Коментарі

Please read the guidelines before commenting.


  • 0
    Javdet  commented on Березень 8, 2024, 12:11 після полудня

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