Katkat
Back

Largest Sum of a Non-Empty Contiguous Subarray

LinkedInSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Given an integer array, return the largest sum of any non-empty contiguous subarray, including arrays in which every number is negative. This classic phone-screen problem tests efficient array processing and careful handling of edge cases such as all-negative input.

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

Function Signature

def max_subarray_sum(nums: list[int]) -> int:

Rules

  • A subarray is a non-empty run of consecutive elements; a single element is a valid subarray.
  • The empty subarray is not allowed, so if every element is negative, the answer is the largest single element.
  • Return only the largest sum, not the subarray. If several subarrays reach it, the returned value is the same.

Constraints

  • 1 <= len(nums) <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • every subarray sum therefore lies between -10^9 and 10^9

Examples

Example 1

Input: nums = [4, -6, 2, 3, -1, 5, -9, 1]
Output: 9

[2, 3, -1, 5] sums to 9. Extending it to the left through 4, -6 lowers the sum to 7, and extending it to the right adds -9 first.

Example 2

Input: nums = [-3, -1, -2]
Output: -1

The empty subarray is not allowed, so the best choice is the single element -1.

Example 3

Input: nums = [5, -2, 5]
Output: 8

Keeping the -2 is worth it because it connects the two 5s: 5 + (-2) + 5 = 8.