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)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store