Maximum Subarray · Interview Problem

Leetcode

maximum-subarray

Medium

Arrays

Dynamic Programming

Divide and Conquer

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

Acceptance 33%

Also Available On

Other platform versions and source mappings for the same problem.

Maximum Subarray Problem

Problem Statement

Core description from the backend problem record.

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

Example: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

An integer array nums of length n.

An integer representing the maximum sum of a contiguous subarray.

1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4

Examples

Sample cases returned by the problem API.

Example 1

Input

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

Output

Explanation

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

Loading Preptin