Maximum Subarray

medium

Given an integer array nums, find the subarray with the largest sum, and return its sum.

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

Test Cases

Copy an input into the main harness and Run to verify

Input

nums = [-2,1,-3,4,-1,2,1,-5,4]

Expected Output

6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Input

nums = [1]

Expected Output

1

Input

nums = [5,4,-1,7,8]

Expected Output

23

Hint 1 — click to reveal

Kadane's algorithm: keep a running sum, but drop it when it goes negative.

Hint 2 — click to reveal

A negative running sum can only hurt a future subarray, so reset it.

Java Compiler