dsa · medium

Maximum Subarray (Kadane)

GreyOrangeArrayDynamic Programming

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

Arguments

**Example 1:** `` Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 ` **Example 2:** ` Input: nums = [1] Output: 1 ``

Constraints

1 <= nums.length <= 10^5 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[-2,1,-3,4,-1,2,1,-5,4]

Expected:
6

Example 2

Input:
[1]

Expected:
1

Open in the Dojo editor