# The Output Peak

> One stretch outpaced all the others.

Canonical URL: <https://datadriven.io/problems/the_output_peak>

Domain: Python · Difficulty: hard · Seniority: L5

## Problem

Given a list of integers (possibly negative), find the contiguous subarray with the largest sum. Return a 2-element list [sum, subarray]. If multiple subarrays tie for max sum, return the earliest (smallest start index).

## Worked solution and explanation

### Why this problem exists in real interviews

This extends the classic **maximum subarray sum** (Kadane's algorithm) by requiring the actual subarray to be returned alongside the sum. It tests whether candidates can track indices while running the greedy algorithm.

> **Trick to Solving**
>
> Kadane's algorithm tracks the current sum and resets when it drops below zero. To also capture the subarray, track the start index of the current candidate subarray and update the best start/end whenever the global max is beaten.

---

### Break down the requirements

#### Step 1: Initialize tracking variables

Set `current_sum` to the first element. Track `best_sum`, `best_start`, `best_end`, and `current_start`.

#### Step 2: Extend or restart the current subarray

At each index, either extend the current subarray (add the element) or start fresh if the current sum plus the element is less than the element alone.

#### Step 3: Update the global best

Whenever `current_sum` exceeds `best_sum`, update `best_sum` and record the current start and end indices.

#### Step 4: Return both the sum and the subarray

Slice the original array from `best_start` to `best_end + 1`.

---

### The solution

**Kadane's algorithm with index tracking**

```python
def max_subarray(nums):
    best_sum = nums[0]
    current_sum = nums[0]
    best_start = 0
    best_end = 0
    current_start = 0
    for i in range(1, len(nums)):
        if current_sum + nums[i] < nums[i]:
            current_sum = nums[i]
            current_start = i
        else:
            current_sum += nums[i]
        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = i
    result = nums[best_start:best_end + 1]
    return best_sum, result
```

> **Time and Space Complexity**
>
> **Time:** O(n) with a single pass through the array.
> 
> **Space:** O(1) beyond the returned subarray slice.

> **Interviewers Watch For**
>
> Can you explain why resetting `current_start = i` when starting fresh is correct? It marks the beginning of a new candidate subarray. If this candidate later beats the best, both its start and end are recorded.

> **Common Pitfall**
>
> Not handling all-negative arrays. Kadane's still works because the best subarray is the single least-negative element, but some implementations that reset to 0 would incorrectly return 0.

---

## Common follow-up questions

- What if you needed the maximum subarray of exactly length k? _(Tests the sliding window approach instead of Kadane's.)_
- How would you find the maximum circular subarray sum? _(Tests computing both the max subarray and the min subarray, then comparing total-minus-min with max.)_
- What if the array were 2D and you needed the maximum sum sub-rectangle? _(Tests the O(n^2 * m) approach using Kadane's on column prefix sums.)_
- What if negative values could be flipped to positive with a budget of k flips? _(Tests greedy or DP extensions to the base algorithm.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_output_peak)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.