noodleProblems/
Maximum Subarray
#61

Maximum Subarray

AlgorithmmediumArrayDivide And ConquerDynamic Programming

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

A subarray is a contiguous, non-empty slice of the array.

Example cases

  • mixed
    in nums = [-2,1,-3,4,-1,2,1,-5,4]
    out 6
    The subarray [4, -1, 2, 1] has the largest sum, 6.
  • single
    in nums = [1]
    out 1
  • all positive
    in nums = [5,4,-1,7,8]
    out 23
    The whole array is the best subarray.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
Saved
nums =
[-2,1,-3,4,-1,2,1,-5,4]