Эта задача — хороший и простой пример применения динамического программирования. В некоторых задачах динамического программирования нам приходится создавать массив (скажем, dp) размера = n. Затем обновите все элементы с помощью «цикла for», чтобы отразить (временно) оптимальные решения. В этом вопросе, хотя динамическое программирование — это подход, нам нужно только сохранить две переменные (g_max и s_max) и только слой «цикла for». В результате сложность может быть линейной (т.е. O(n)).
Примечание. Вывод не может быть пустым. Другими словами, если все элементы равны нулю, мы должны дать Leetcode максимальное число среди входных данных.
Код Python: https://github.com/j611062000/leetcode/blob/master/Easy/53_Maximum%20Subarray.py
