DP
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
res = nums[0]
dp = [nums[0] for i in range(n + 1)]
for i in range(1, n):
dp[i] = max(0, dp[i - 1]) + nums[i]
res = max(dp[i], res)
return res