```
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
"""
Dynamic programming
"""
assert nums != [], "Empty array!"
if len(nums) == 1:
return nums[0]
max_sum = nums[0]
max_sum_end = nums[0]
for num in nums[1:]:
max_sum_end = max(max_sum_end + num, num)
max_sum = max(max_sum, max_sum_end)
return max_sum
```