Maximum Subarray Sum with a Length Cap
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Maximum Subarray Sum with a Length Cap
Implement `max_subarray_at_most_k(nums, k)`. Return the maximum sum of any nonempty contiguous subarray whose length is at most `k`.
The nonempty interpretation is an explicit pedagogical assumption because the source states a maximum contiguous-subarray sum with a length cap but does not define whether choosing no elements is allowed.
## Function Contract
`max_subarray_at_most_k(nums: list[int], k: int) -> int`
## Constraints
- `1 <= len(nums) <= 200000`
- `1 <= k <= len(nums)`
- `-10^9 <= nums[i] <= 10^9`
- The result may exceed 32-bit signed integer range.
## Examples
### Example 1
```text
Input: nums = [2, -1, 3, 4, -5], k = 3
Output: 7
```
The subarray `[3, 4]` has length `2` and sum `7`.
### Example 2
```text
Input: nums = [-4, -2, -7], k = 2
Output: -2
```
Because the selected subarray must be nonempty, the best choice is the single value `-2`.
Overview: Compute the maximum sum of a nonempty contiguous subarray whose length cannot exceed a given cap. The prompt fixes negative-only behavior, integer-width expectations, and two exact examples for later cross-language console verification.
Read the full Oracle Software Engineer interview experience this question came from
Given an integer array nums and an integer k, return the maximum sum of any nonempty contiguous subarray whose length is at most k. The nonempty interpretation is an explicit pedagogical assumption because the source states a maximum contiguous-subarray sum with a length cap but does not say whether choosing no elements is allowed. The exact result may exceed 32-bit signed integer range.
Constraints
- 1 <= len(nums) <= 200,000
- 1 <= k <= len(nums)
- -10^9 <= nums[i] <= 10^9
- The selected contiguous subarray must be nonempty.
- The result may exceed 32-bit signed integer range.
Examples
Input: ([2, -1, 3, 4, -5], 3)
Expected Output: 7
Explanation: The length-two subarray [3, 4] has the maximum sum 7.
Input: ([-4, -2, -7], 2)
Expected Output: -2
Explanation: The nonempty requirement selects the single value -2.
Hints
- Express every subarray sum as a difference of two prefix sums.
- For each right boundary, maintain the minimum eligible prefix sum from the previous k positions.