Розбір для Максимальна сума підмасиву
Памʼятайте, що цей розбір слід використовувати лише коли ви застрягли, і не копіювати код з нього. Будь ласка, поважайте автора задачі та автора розбору.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Розбір розв'язку
Це класична задача, яка розв'язується алгоритмом Кадане (Kadane's algorithm) — окремий випадок динамічного програмування.
Нехай ~dp[i]~ — максимальна сума відрізка, що закінчується саме в позиції ~i~. Тоді:
dp[i] = \max(ai,\ dp[i-1] + ai)
Інтуїція: якщо сума попереднього відрізка ~dp[i-1]~ від'ємна, вигідніше почати новий відрізок з елемента ~a_i~ (тобто "відкинути" від'ємний "хвіст"); інакше — вигідно продовжити попередній відрізок.
Відповідь — максимум серед усіх значень ~dp[i]~.
Оскільки для обчислення ~dp[i]~ потрібне лише попереднє значення ~dp[i-1]~, масив ~dp~ можна не зберігати повністю, а обійтися однією змінною. Складність алгоритму — ~O(n)~ за часом і ~O(1)~ за додатковою пам'яттю.
Коментарі