Subarray Signal

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Amazon

Problem

A metrics export hands you per-interval signal deltas as a list of integers, some positive and some negative. Return the largest total any contiguous run of at least one interval can reach.

One stretch carries the strongest signal.

Example 1

Input:

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

Output:

6

Example 2

Input:

nums = [-3,-5,-1,-8]

Output:

-1

Worked solution and explanation

What this really is

Strip off the signal-monitoring costume and this is maximum contiguous subarray. Anyone who has seen it writes the single linear scan. The people who haven't reach for an O(n^2) pair loop, or worse, seed the best total at 0 and quietly break every all-negative export. The real probe is whether you notice the run must hold at least one interval, which is exactly what a 0 seed forgets. Get it wrong and [-3, -5, -1, -8] reports 0, a run that never happened.

How you get there

Step 1: Anchor on the first element

Seed both current_sum and best_sum to nums[0], not 0. That single choice lets an all-negative input return its least-negative element instead of a phantom empty run worth 0.

Step 2: Extend or restart, element by element

For every later element, either extend the run you are carrying or restart at this element, whichever total is larger. The restart is the whole algorithm: a negative prefix is dead weight, so you drop it the moment it costs you.

Step 3: Capture the global best as you scan

After each update, fold current_sum into best_sum. The best run can end anywhere, so you capture it as you pass, not at the finish line.

The solution

Kadane's algorithm for the strongest contiguous run
def subarray_signal(nums):
    current_sum = nums[0]
    best_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        best_sum = max(best_sum, current_sum)
    return best_sum

One pass, two integers of state.

Common follow-up questions