How should I practice Maximum Subarray?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Maximum Subarray associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Maximum Subarray

Microsoft● EasyNEW GRADONSITE INTERVIEW

Learn

Problem statement

Given an integer array nums, return the largest possible sum of a nonempty contiguous subarray.

Function

maxSubArray(nums: int[]) → long

Examples

Example 1

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

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

Example 2

nums = [1]return = 1

The only nonempty subarray is the single element.

Example 3

nums = [-8,-3,-6,-2,-5,-4]return = -2

When every value is negative, the best nonempty subarray is the largest individual value.

Constraints

1 <= nums.length <= 100000.
-1000000000 <= nums[i] <= 1000000000.
The answer fits in a signed 64-bit integer.