Skip to main content

Maximum Subarray

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

Problems5 / 152
Sign in

Maximum Subarray

MEDIUMArrayDynamic Programming

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

Example 1

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

Example 2

Input:  nums = [1]
Output: 1
Show hint

Use Kadane's algorithm: keep track of current sum and maximum sum. Reset current sum to 0 if it becomes negative.

Draft saves automatically

Loading editor...

Submit also runs hidden tests
nums =
[-2,1,-3,4,-1,2,1,-5,4]
Expected
6
Run with your own input (JSON)