Maximized Capacity Window — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums. A *capacity window* is any non‑empty contiguous segment of nums. The capacity of a window equals the sum of all elements inside it. Your task is to determine the maximum possible capacity among all windows. Output this maximum sum. The solution must run in linear time relative to the length of the array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximized Capacity Window"
WHY DOES IT MATTER?
Maximum sub‑array problems appear in performance monitoring, financial profit calculations, and signal processing, where identifying the most profitable or highest‑impact contiguous segment is essential. Mastering this pattern equips engineers to turn quadratic brute‑force scans into linear‑time solutions, a core skill for scaling algorithms.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the optimal window ending at position i depends only on the optimal window ending at i‑1. By discarding all earlier windows and keeping just the best local sum, we reduce both time and space from O(n²) and O(n) to O(n) and O(1).
REAL-WORLD CONNECTION
Think of a streaming log of server latency measurements; the maximum capacity window corresponds to the longest period where latency spikes cumulatively, helping pinpoint the worst‑performing interval without storing the entire history.
During an interview, write the two‑variable version first, then add the index‑tracking logic only if the prompt asks for the window boundaries. This keeps the solution clean and avoids premature optimization.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem of finding the maximum capacity window is a classic instance of the maximum sub‑array sum problem. The naïve solution enumerates every possible contiguous segment, computes its sum, and tracks the largest, which incurs O(n²) time because each of the O(n) start positions can extend to O(n) end positions. For large inputs this quickly becomes infeasible as the number of operations grows quadratically.
The optimal paradigm leverages the principle of dynamic programming in a greedy fashion, famously known as Kadane’s algorithm. While scanning the array once, we maintain two variables: the best sum ending at the current index (local maximum) and the overall best seen so far (global maximum). At each step we decide whether to extend the previous window by adding the current element or to start a new window from the current element alone. This decision is made by comparing the current element with the sum of the current element plus the previous local maximum. The algorithm thus collapses the exponential number of sub‑array possibilities into a linear pass, guaranteeing O(n) time and O(1) extra space.
The correctness stems from the optimal substructure property: any optimal window ending at position i either includes the optimal window ending at i‑1 (if that sum is positive) or starts fresh at i (if the previous sum would diminish the total). By iteratively applying this rule, the algorithm ensures that the global maximum captured at the end of the scan is indeed the maximum possible capacity across all windows.
Interview Questions on This Problem
Q1How would you modify Kadane’s algorithm to also return the start and end indices of the maximum capacity window?
Track additional variables for the potential start index of the current window and update them when you reset the local sum to the current element. Whenever the global maximum is updated, record the current index as the end and the stored start as the beginning of the optimal window.
Q2Can Kadane’s algorithm handle arrays that contain only negative numbers? What would be the result?
Yes. If all numbers are negative, the algorithm will never reset the local sum to a larger value, so the global maximum ends up being the largest (least negative) single element, which is the correct maximum sub‑array sum.
Q3Explain how you could extend the maximum capacity window problem to find the maximum sum of a sub‑array with length at most K.
Use a sliding window of size up to K while maintaining a prefix‑sum array. For each index i, compute the best sum ending at i by subtracting the minimum prefix sum among the last K positions, yielding an O(n) solution with O(K) auxiliary storage.
Examples
Input
6 2 -1 3 -4 5 -2
Output
5
Explanation: All possible windows are examined. The window consisting of the single element 5 yields the largest sum (5). No longer window surpasses this value, so the answer is 5.
Input
4 -3 -2 -5 -1
Output
-1
Explanation: Every element is negative. The window with the highest sum is the one containing the least negative number, which is -1. Hence the maximum capacity is -1.
Input
5 1 2 3 4 5
Output
15
Explanation: Because all numbers are positive, extending the window never reduces the sum. The window covering the entire array gives the sum 1+2+3+4+5 = 15, which is maximal.
Constraints
- 1 <= nums.length <= 100000
- -10^9 <= nums[i] <= 10^9
- The answer fits in a 64‑bit signed integer.
Optimal Approach & Strategy
Use Kadane’s algorithm: iterate once, updating a local maximum (extend or restart) and a global maximum; this runs in O(n) time with O(1) extra space.
Brute Force Approach
Enumerate every possible start and end index, compute each window's sum, and keep the maximum; this costs O(n²) time.
Verified Code Solutions
function solution(nums) {
let maxSum = -Infinity;
let currentSum = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
currentSum += nums[right];
while (currentSum < 0) {
currentSum -= nums[left];
left++;
}
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}class Solution {
public:
int solution(vector<int>& nums) {
int maxSum = INT_MIN;
int currentSum = 0;
int left = 0;
for (int right = 0; right < nums.size(); right++) {
currentSum += nums[right];
while (currentSum < 0) {
currentSum -= nums[left];
left++;
}
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
};class Solution {
public int solution(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
int left = 0;
for (int right = 0; right < nums.length; right++) {
currentSum += nums[right];
while (currentSum < 0) {
currentSum -= nums[left];
left++;
}
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
}def solution(nums):
max_sum = float('-inf')
current_sum = 0
left = 0
for right in range(len(nums)):
current_sum += nums[right]
while current_sum < 0:
current_sum -= nums[left]
left += 1
max_sum = max(max_sum, current_sum)
return max_sumfunction solution(nums) {
let maxSum = -Infinity;
let currentSum = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
currentSum += nums[right];
while (currentSum < 0) {
currentSum -= nums[left];
left++;
}
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.