Find the Maximum Sum of a Contiguous Subarray
Company: Omnissa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Find the Maximum Sum of a Contiguous Subarray
Given a nonempty integer array `nums`, return the largest possible sum of a nonempty contiguous subarray.
Implement:
```text
maximumSubarraySum(nums) -> integer
```
The selected subarray must contain at least one element. All intermediate sums fit in a signed 64-bit integer.
## Constraints
- `1 <= nums.length <= 1,000,000`
- `-10^9 <= nums[i] <= 10^9`
## Examples
### Example 1
```text
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
output = 6
```
The contiguous subarray `[4, -1, 2, 1]` has sum 6.
### Example 2
```text
nums = [-8, -3, -6]
output = -3
```
An empty subarray is not allowed, so the best choice is the single value `-3`.
Overview: Compute the maximum sum of any nonempty contiguous subarray, including all-negative inputs and large 64-bit totals. The exercise calls for a linear scan with constant auxiliary space and makes the nonempty-selection rule explicit.
Read the full Omnissa Software Engineer interview experience this question came from
Given a nonempty integer array nums, return the largest sum of any nonempty contiguous subarray. All intermediate sums fit in a signed 64-bit integer.
Constraints
- 1 <= nums.length <= 1,000,000
- -10^9 <= nums[i] <= 10^9
- The selected subarray is contiguous and nonempty.
- All intermediate sums fit in signed 64-bit range.
Examples
Input: ([-2, 1, -3, 4, -1, 2, 1, -5, 4],)
Expected Output: 6
Explanation: The interior subarray [4, -1, 2, 1] sums to 6.
Input: ([-8, -3, -6],)
Expected Output: -3
Explanation: The nonempty rule selects the single value -3.
Hints
- At each index, choose whether to extend the previous subarray or start a new one.
- Initialize from the first value so negative-only arrays remain correct.