Опять алгоритмы...

Вы заметили, что я люблю тему алгоритмов? Я заметил...

Нужны ли алгоритмы программистам?

Задачи — это пища для ума. Кто-то голоден? 😁

Предлагаю задачу: найти максимально возможную сумму последовательных элементов массива.

Примеры:

• [-1, 3, 1, -5, 5, 4, -4, 2] = 9 [5, 4]
• [-3, 1, 2, -2, 0, 3, -4, 2] = 4 [1, 2, -2, 0, 3]
• [-1, 6, -4, 6] = 8 [6, -4, 6] и т д

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

Обязательно попробуйте самостоятельно.

Существует как минимум три подхода к решению, но лучший, это вариант, который делает минимальное количество действий.

Можно решить тремя циклами — получить O(n³)

Можно двумя — O(n²)

Можно одним -— O(n)

Вот примерное время выполнения

╔═════╦═════╦══════╦════════╗
║    n║ O(n)║ O(n²)║   O(n³)║
╠═════╬═════╬══════╬════════╣
║ 1000║  0ms║   1ms║   183ms║
╠═════╬═════╬══════╬════════╣
║ 2000║  0ms║   5ms║  1444ms║
╠═════╬═════╬══════╬════════╣
║ 3000║  0ms║  11ms║  4839ms║
╠═════╬═════╬══════╬════════╣
║ 4000║  0ms║  19ms║ 11434ms║
╠═════╬═════╬══════╬════════╣
║ 5000║  0ms║  30ms║ 22289ms║
╠═════╬═════╬══════╬════════╣
║ 6000║  0ms║  44ms║ 38514ms║
╠═════╬═════╬══════╬════════╣
║ 7000║  0ms║  59ms║ 61070ms║
╠═════╬═════╬══════╬════════╣
║ 8000║  0ms║  77ms║ 91663ms║
╠═════╬═════╬══════╬════════╣
║ 9000║  0ms║  97ms║131100ms║
╚═════╩═════╩══════╩════════╝

Данные для O(n) воспринимайте как бесконечно малую величину.

Лучше, чем за О(n) эту задачу решить нельзя т к нужно просмотреть все элементы массива.

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

Оптимизация в таких делах решает.

Исходники на GitHub

А вот вопрос про нужность алгоритмов остаётся открытым 🤷🏼‍♂️