InternDoor

Best stretch of numbers

Mediumarrays · dynamic programming

Reported in interviews at (where)

You are given a list of whole numbers nums, some of them negative. A stretch is one or more numbers that sit next to each other in the list.

Return the largest sum any stretch can have.

Trying every stretch takes too long for a long list: aim for one pass.

Example 1
Input
nums = [-3,5,-1,6,-8,2]
Output
10

The stretch 5, -1, 6 adds up to 10.

Example 2
Input
nums = [-4,-2,-7]
Output
-2

Every number is negative, so the best stretch is the single -2.

Limits

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

Hints

Hint 1

Walk the list once, keeping the best sum of a stretch that ends where you stand.

Hint 2

A stretch ending here either starts here or extends the best one ending just before.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.