Problem overview
The method maxSum(nums, k) receives an array of integers and a positive integer k. A subarray is a run of neighboring elements, and this problem only looks at subarrays of length exactly k. The goal is to find the one with the largest sum, and to return where it sits: an array with its first and last index, [start, end]. The method returns the positions, not the sum itself.
In the example, nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3. There are six windows of length 3:
| Start index | Window | Sum |
|---|---|---|
| 0 | 5, 6, 1 | 12 |
| 1 | 6, 1, 2 | 9 |
| 2 | 1, 2, 6 | 9 |
| 3 | 2, 6, 6 | 14 |
| 4 | 6, 6, 4 | 16 |
| 5 | 6, 4, 3 | 13 |
The best window starts at index 4 and ends at index 6, with a sum of 16, so the answer is [4, 6].
Approach
The direct approach is to try every window. A window of length k can start at index 0, 1, 2 and so on, up to the last index that still leaves room for k elements, which is nums.length - k. For each start, add up its k elements, compare the sum with the best sum so far and remember the window if it is better.
That is nums.length - k + 1 windows with k additions each, so the work is O(n * k), where n is the array length. This is the brute-force version, and it is the one this lesson writes. It is easy to get right, and it leaves a clear target for the faster version (the sliding window) that comes next in the course: the sums of neighboring windows share k - 1 elements, so the sum does not need to be recomputed from scratch.
Step by step
- Keep the best sum so far in
maxSum. Start it atNumber.NEGATIVE_INFINITY, which is smaller than any real sum. The first window then always replaces it, even when every number in the array is negative. Starting at0would be a bug, since a window of negative numbers never beats0. - Keep the best window in
answer, starting as an empty array. It will hold the start and end indices. - Loop over the window starts with
ifrom0tonums.length - kinclusive. The condition is<=because the last window begins exactly atnums.length - k. With<, the last window would be skipped. - Reset
sumto0for every window. It is declared inside the loop, so each start adds up its own elements. - Add up the window with an inner loop. The variable
idxruns fromiup to but not includingi + k, which visits exactlykpositions. - Add
nums[idx]tosum. - Compare with the best. When
sum > maxSum, updatemaxSumand setanswerto[i, i + k - 1]. The strict>means that when two windows tie, the earlier one stays. - Return
answeronce both loops are done.
The solution in JavaScript
class Solution {
maxSum(nums, k) {
let maxSum = Number.NEGATIVE_INFINITY;
let answer = [];
for (let i = 0; i <= nums.length - k; i++) {
let sum = 0;
for (let idx = i; idx < i + k; idx++) {
sum += nums[idx];
}
if (sum > maxSum) {
maxSum = sum;
answer = [i, i + k - 1];
}
}
return answer;
}
}
A few JavaScript details:
- The local variable shares the method's name. Inside the class,
maxSumis a method name, but thelet maxSumin the method body is a separate local variable. They do not clash, because methods are reached throughthis.maxSum, never by the bare name. - Replacing the array.
answer = [i, i + k - 1]builds a new two-element array. The old one is discarded, so nothing needs to be cleared. - Numbers are doubles. The sums are exact as long as they stay below
Number.MAX_SAFE_INTEGER(about 9 quadrillion), which is far beyond typical lesson inputs.
Complexity
Time: O(n * k). The outer loop runs n - k + 1 times, and the inner loop adds k numbers each time. If k is close to n, there are few windows but each is long, and if k is small, there are many short windows. The product is largest when k is about half of n.
Space: O(1). The method keeps a few numbers and a two-element array.
The faster idea: sliding window
Two neighboring windows differ by one element on each side. Window 3 (2, 6, 6) becomes window 4 (6, 6, 4) by dropping the 2 and adding the 4. So the sum of the next window is the old sum, minus the element that leaves, plus the element that enters. The following sketch finds the same answer in O(n) time:
function maxSumWindow(nums, k) {
let window = 0;
for (let i = 0; i < k; i++) window += nums[i];
let best = window;
let start = 0;
for (let i = k; i < nums.length; i++) {
window += nums[i] - nums[i - k];
if (window > best) {
best = window;
start = i - k + 1;
}
}
return [start, start + k - 1];
}
For the lesson's example it returns [4, 6]. Unlike the brute force, it assumes nums.length >= k.
Edge cases and common mistakes
- All numbers negative. For
[-3, -1, -2, -5]andk = 2the window sums are -4, -3 and -7, so the answer is[1, 2]. This works becausemaxSumstarts at negative infinity. - Ties. For
[2, 2, 2, 2]andk = 2every window sums to 4. The answer is[0, 1], the earliest, because later windows are not strictly greater. kequals the array length. There is exactly one window:[1, 2, 3]withk = 3gives[0, 2].k = 1. Each element is its own window, so the answer is the position of the largest element:[4, -1, 4]gives[0, 0].klarger than the array.nums.length - kis negative, so the outer loop never runs and the method returns the empty array[].- Off by one at the window end. The window that starts at
iends ati + k - 1, noti + k. - Forgetting to reset
sum. Ifsumis declared outside the outer loop, each window adds onto the previous total.
Testing
nums = [5, 6, 1, 2, 6, 6, 4, 3],k = 3gives[4, 6].nums = [-3, -1, -2, -5],k = 2gives[1, 2].nums = [2, 2, 2, 2],k = 2gives[0, 1].nums = [7],k = 1gives[0, 0].nums = [1, 2],k = 3gives[].
