How should I practice Maximum Subarray Sum?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Straive online assessment problems in FastPrep.

Is Maximum Subarray Sum associated with Straive?

FastPrep tags this as a Straive online assessment coding practice problem when the problem catalog has that company and stage context.

Maximum Subarray Sum

Straive● MediumNEW GRADOA

Problem statement

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

Elements may be negative. When every element is negative, return the largest element. Return the result as a 64-bit integer.

Follow-up

After finding a linear-time solution, also solve the problem using divide and conquer.

Function

maxSubArray(nums: int[]) → long

Examples

Example 1

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

The contiguous subarray [4,-1,2,1] has sum6. Exhaustive interval enumeration gives no larger sum.

Example 2

nums = [1]return = 1

The only nonempty subarray is [1], so the result is1.

Example 3

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

The entire array [5,4,-1,7,8] has sum23, the largest among all15nonempty intervals.

Constraints

1 <= nums.length <= 100000.
-10000 <= nums[i] <= 10000.