# Subarray Signal

> One stretch carries the strongest signal.

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of integers (possibly negative), return the maximum sum achievable by any contiguous subarray of at least one element.

## Worked solution and explanation

### Why this problem exists in real interviews

Maximum subarray sum is the classic **Kadane's algorithm** problem. It tests dynamic programming intuition: at each position, decide whether to extend the current subarray or start fresh.

> **Trick to Solving**
>
> Kadane's algorithm: maintain `current_sum` (best subarray ending here) and `best_sum` (global best). At each element, `current_sum = max(num, current_sum + num)`. If extending the subarray would be worse than starting over, start over.

---

### Break down the requirements

#### Step 1: Initialize current and best sums to the first element

The subarray must contain at least one element.

#### Step 2: At each position, extend or restart

If `current_sum + num` is better than `num` alone, extend. Otherwise, start a new subarray at `num`.

#### Step 3: Track the global best

Update `best_sum` whenever `current_sum` exceeds it.

---

### The solution

**Kadane's algorithm for maximum contiguous subarray sum**

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

> **Time and Space Complexity**
>
> **Time:** O(n) with a single pass. Each element is visited once.
> 
> **Space:** O(1). Two integer variables.

> **Interviewers Watch For**
>
> Naming this as Kadane's algorithm shows you know the pattern. The O(n) solution is expected; O(n^2) brute force is a red flag for medium-level candidates.

> **Common Pitfall**
>
> Initializing `best_sum` to 0 instead of `nums[0]`. For all-negative lists like `[-3, -2, -1]`, the answer is -1, not 0.

---

## Common follow-up questions

- How would you also return the start and end indices of the subarray? _(Tests tracking indices alongside the sum updates.)_
- What if the problem allows an empty subarray (sum = 0)? _(Tests comparing the result against 0 and returning the larger.)_
- How would you find the maximum circular subarray sum? _(Tests computing both max subarray and min subarray, then using `total - min` for the wrap-around case.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/subarray_signal)
- [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.