How should I practice Maximum Subarray?

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

Is Maximum Subarray associated with Upstart?

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

Maximum Subarray

Upstart● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Given a nonempty integer array nums, return the largest sum of any nonempty contiguous subarray. A subarray uses consecutive elements in their original order.

For this exercise, assume the result is an exact signed 64-bit integer. You must choose at least one element, including when all values are negative.

Function

maxSubarraySum(nums: int[]) → long

Examples

Example 1

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

Interior maximum across several positive runs.

Example 2

nums = [-8,-3,-6]return = -3

All negative must not return empty zero.

Example 3

nums = [5]return = 5

Single positive.

Constraints

1 <= nums.length <= 1000.
-10^9 <= nums[i] <= 10^9.
Use signed 64-bit arithmetic for running sums and the result.