Largest Sum of a Non-Empty Contiguous Subarray
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `nums`, return the largest sum of any non-empty contiguous subarray.
### Function Signature
```python
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**
```text
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**
```text
Input: nums = [-3, -1, -2]
Output: -1
```
The empty subarray is not allowed, so the best choice is the single element `-1`.
**Example 3**
```text
Input: nums = [5, -2, 5]
Output: 8
```
Keeping the `-2` is worth it because it connects the two 5s: `5 + (-2) + 5 = 8`.
Overview: 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.
Read the full LinkedIn Software Engineer interview experience this question came from
Given an integer array `nums`, return the largest sum of any non-empty contiguous subarray.
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 itself. If several subarrays reach the largest sum, the returned value is the same, so no tie-break is needed.
### Function Signature
```python
def max_subarray_sum(nums: list[int]) -> int:
```
In Java the method takes `int[] nums` and returns `long`; in C++ it takes `const std::vector<int>& nums` and returns `long long`.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^4 <= nums[i] <= 10^4`
- every subarray sum therefore lies between `-10^9` and `10^9`, so no sum exceeds 2^31 - 1 in magnitude; the 64-bit return types in Java and C++ are only a safe width.
### Examples
**Example 1**
```text
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**
```text
Input: nums = [-3, -1, -2]
Output: -1
```
The empty subarray is not allowed, so the best choice is the single element `-1`.
Constraints
- 1 <= len(nums) <= 10^5
- -10^4 <= nums[i] <= 10^4
- Every subarray sum lies between -10^9 and 10^9 (never exceeds 2^31 - 1 in magnitude); Java returns long and C++ returns long long
Examples
Input: ([7],)
Expected Output: 7
Explanation: Singleton positive array: the only subarray is [7].
Input: ([-5],)
Expected Output: -5
Explanation: Singleton negative array: the single element is the only non-empty subarray, so the answer is -5, not 0.
Hints
- A subarray must contain at least one element, so decide what the answer is when every value is negative.
- A negative element inside a run can still be worth keeping when what it connects on both sides outweighs it, as in [5, -2, 5].
- Only the sum is returned, so different subarrays that tie for the largest sum need no special handling.