Автор, розробник, автор розбору: Андрій Столітній
В умові задачі написано, що нам треба, щоб кожен підвідрізок довжини більше ніж 1 кожного з фінальних масивів мав невід'ємну суму. Можна помітити, що достатньо, щоб всі підвідрізки довжиною та мали невід'ємну суму. Тому що кожний відрізок довжини більше ніж можна розбити на підвідрізки довжини і , а якщо вони всі мають невід'ємну суму, то весь відрізок має невід'ємну суму.
Також розбиття масиву на менші масиви можна робити неявно, усуваючи елементи з масиву. Будемо підтримувати значення динамічного програмування, де dp_{i,j} буде означати максимальну кількість елементів, яку ми можемо залишити з префіксу довжини , та ми залишили останні елементів, тобто , i-1, ..., i-j+1. Тоді, коли додаємо новий елемент, ми можемо або залишати його, або прибирати. Так як ми не розглядаємо підвідрізки довжини більше, ніж , то можемо зробити стани dp_{i,0}, dp_{i,1}, dp_{i,2}, dp_{i,3} —
не взяли елемент ,
взяли елемент , не взяли i-1,
взяли , i-1, не взяли i-2,
взяли , i-1, i-2, або більше.
Тоді можна зробити такі переходи:
Тоді відповіддю буде
Загальна складність: .