# Maximum Contiguous Subarray

**Problem Statement**

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

**Example 1:**

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

**Example 2:**

Input: nums = [1] Output: 1

**Example 3:**

Input: nums = [5,4,-1,7,8] Output: 23

**Solution**

class Solution: def maxSubArray(self, nums: List[int]) -> int: cur_sum = nums[0] max_sum = nums[0] for val in nums[1:]: if val < 0 and cur_sum < 0: cur_sum = max(cur_sum, val) elif val >= 0 and cur_sum < 0: cur_sum = val else: cur_sum += val max_sum = max(max_sum, cur_sum) return max_sum