```
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
max_sum, cur_sum = -2**31, 0
i, j = 0, 0
while i < n and j < n:
cur_sum += nums[j]
max_sum = max(cur_sum, max_sum)
if cur_sum < 0: # it means sum(nums[i:j+1])<0, so we can skip this segment
j += 1
i = j
cur_sum = 0
else:
j += 1
return max_sum
```