Алгоритми та структури даних · Middle · Запитання 47 з 75
У чому ідея алгоритму Кадане для максимальної суми підмасиву?
- 1Відсортувати масив і скласти всі додатні числа в ньому
- ✓Правильна відповідь: Найкраща сума, що закінчується тут: продовжити чи почати знову
- 3Перевірити суму кожного можливого підмасиву окремо
Пояснення
cur = Math.max(x, cur + x), best = Math.max(best, cur). Від'ємна поточна сума лише шкодить, тож її відкидають. Один прохід O(n) замість O(n²) для всіх підмасивів.