Quick 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.

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

  1. Express every subarray sum as a difference of two prefix sums.
  2. For each right boundary, maintain the minimum eligible prefix sum from the previous k positions.

Loading coding console...

Show the approach

Approach

Let prefix[r] be the sum before index r. A subarray ending just before r and starting at l has sum prefix[r] - prefix[l], with r-k <= l < r. For each right boundary, a monotonic deque stores eligible prefix indices in nondecreasing prefix-sum order, so its front is the best left boundary. Remove expired indices, score the current right boundary, then insert its prefix while removing no-better suffix candidates. Scoring before insertion preserves the nonempty rule.

Time complexity:
O(n), where n is len(nums).
Space complexity:
O(n) for prefix sums and the monotonic deque.