3. Maximum Subarray

You’re interviewing for a backend/data engineering role at a FAANG-level company. The interviewer describes a real product scenario:

A streaming or marketplace platform records a daily metric for a feature rollout, like:

• daily active user change (+ / -)
• revenue delta (+ / -)
• latency improvement/regression (+ / -)
• user sentiment score changes (+ / -)

These daily deltas are stored in an integer array nums.
Your job is to find the contiguous time window (a continuous range of days) where the platform performed the best overall—meaning the sum of the deltas in that window is maximum.

This is a common coding interview / DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Given an integer array nums, return the maximum sum of any non-empty contiguous subarray.

Input Format

• nums: an array of integers (can contain both positive and negative values)

Output Format

• A single integer: the maximum subarray sum

Examples

Constraints

• 1 <= nums.length <= 100,000
• -10^4 <= nums[i] <= 10^4
• Subarray must be contiguous
• Subarray must be non-empty