The maximum sum of a sequence with the end index j is the sum of A[0:j + 1] minus the minimum sum of A[0:i] for any i <= j.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
s = 0
min_s = 0
max_s = nums[0]
for num in nums:
s += num
max_s = max(max_s, s - min_s)
min_s = min(min_s, s)
return max_s