# Maximum Subarray — LC Medium

Companies: Amazon, Linkedin, Apple

53. Maximum Subarray

Given an integer array `nums`

, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*.

A **subarray** is a **contiguous** part of an array.

**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

**Constraints:**

`1 <= nums.length <= 105`

`-104 <= nums[i] <= 104`

**Follow up:** If you have figured out the `O(n)`

solution, try coding another solution using the **divide and conquer** approach, which is more subtle.

My first approach: array, pointers

as you progress through the array, do a cumulative sum and if that cumulative sum becomes negative, initialize the cumulative sum to zero and restart this.

e.g) [-2,1,-3,4,-1,2,1,-5,4]

lets use the maxSum, curSum to denote two keeper variable with current sum and max sum. if the curSum becomes negative, reinitialize the cur Sum to zero, and replace the max sum as we go through the iteration.

curSum = 0, maxSum = 0

# run 1: -2

curSum = 0 + (-2) = -2

maxSum = max(0, -2) = 0

# run 2: 1

curSum < 0, so re initialize the curSum to 0 (from run 2)

curSum = 0 + 1 = 1

maxSum = max(0, 1) = 1

# run 3: -3

curSum = 1 + (-3) = -2

maxSum = max(1, -2) = 1

# run 4: 4

curSum <0, so re initialize the curSum to 0 (from run 3)

curSum = 0 + 4= 4

maxSum = max(1, 4) = 4

# run 5: -1

curSum = 4 + (-1) = 3

maxSum = max(4, 3) = 4

# run 6: 2

curSum = 3 + 2 = 5

maxSum = max(4, 5) = 5

# run 7: 1

curSum = 5 + 1 = 6

maxSum = max(5, 6) = 6

# run 8: -5

curSum = 6 + (-5) = 1

maxSum = max(6, 1) = 6

# run 9: 4

curSum = 1 + 4 = 5

maxSum = max(6, 5) = 6

therefore. maxSum = 6

code:

`class Solution:`

def maxSubArray(self, nums: List[int]) -> int:

maxSub = nums[0]

curSum = 0

for n in nums:

if curSum < 0: # if the current sub goes to negative,

curSum = 0

curSum += n

maxSub = max(maxSub, curSum)

return maxSub

Time complexity: O(N)

Space complexity: O(1)