Maximum Subarray

Given an array of integers nums, find the non-empty run of consecutive numbers with the largest sum, and return that sum.

Constraints

  • 1 ≤ length of nums ≤ 100,000
  • -10,000 ≤ nums[i] ≤ 10,000

Example 1

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

[4, -1, 2, 1] adds up to 6.

Example 2

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

The whole array.

Example 3

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

The run can't be empty, so the best is the single -1.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –