AlgoLounge

Maximum Subarray

medium

Given an array of integers nums, find the subarray with the largest sum and return the sum.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

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

The subarray [4,-2,2,1,-1,4] has the largest sum 8.

Example 2

Input:  nums = [-1]
Output: -1

Constraints

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
TypeScript
Loading editor…
List of test cases (10)
Case 1
nums = [2,-3,4,-2,2,1,-1,4]
Case 2
nums = [-1]
Case 3
nums = [1,2,3,4,5]
Case 4
nums = [-2,-3,-1,-5]
Case 5
nums = [5]
Case 6
nums = [-5,4,-1,7,-8]
Case 7
nums = [1,-3,2,1,-1]
Case 8
nums = [-1,0,-2]
Case 9
nums = [0,-1,2,-3,4]
Case 10
nums = [5,4,-1,7,8]