Този проблем е добър и лесен пример за прилагане на динамично програмиране. В някои проблеми на динамичното програмиране трябва да създадем масив (да речем dp) с размер = n. След това актуализирайте всички елементи чрез „for цикъл“, за да отразите (временно) оптималните решения. В този въпрос, въпреки че динамичното програмиране е начинът да подходим към него, трябва да запазим само две променливи (g_max и s_max) и само слой от „for цикъл“. В резултат на това сложността може да бъде линейна (т.е. O(n)).
Забележка: Изходът не може да бъде празен. С други думи, ако всички елементи са нула, трябва да дадем на Leetcode максималния брой сред входните данни.
Код на Python: https://github.com/j611062000/leetcode/blob/master/Easy/53_Maximum%20Subarray.py
