Maximum Sum Subarray of Size K
Solve this Problem
Given an array of positive integers
nums and an integer k, find the maximum sum of any contiguous subarray of size exactly k.
Checking every window from scratch works, but it throws away the overlap between consecutive windows — a window sliding one step to the right shares k - 1 of its elements with the window before it. The sliding windowSliding WindowMaintaining a running result over a contiguous range that grows or shrinks one element at a time, instead of recomputing the result for every range from scratch. technique exploits that: keep a running sum and update it in O(1) per step by adding the element that just entered and removing the one that just left.
Test Case 1:
Input:nums = [2, 1, 5, 1, 3, 2], k = 3
Output:9
Explanation:The window [5, 1, 3] (indices 2-4) has the largest sum: 9.
Test Case 2:
Input:nums = [2, 3, 4, 1, 5], k = 2
Output:7
Explanation:The window [3, 4] has the largest sum among all windows of size 2.
Test Case 3:
Input:nums = [4, 2, 1, 7], k = 4
Output:14
Explanation:k equals the array length, so there's only one possible window — the whole array.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁵ - ◆
1 ≤ nums[i] ≤ 10⁴ - ◆
1 ≤ k ≤ nums.length
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int maxSumSubarrayOfSizeK(int[] nums, int k) { |
| 3 | int windowSum = 0; |
| 4 | for (int i = 0; i < k; i++) { |
| 5 | windowSum += nums[i]; |
| 6 | } |
| 7 | int maxSum = windowSum; |
| 8 | for (int i = k; i < nums.length; i++) { |
| 9 | windowSum += nums[i] - nums[i - k]; |
| 10 | maxSum = Math.max(maxSum, windowSum); |
| 11 | } |
| 12 | return maxSum; |
| 13 | } |
| 14 | } |
| 15 |
2
1
5
1
3
2
0
1
2
3
4
5
↑left
↑right
Variables
windowSum
8windowSum = nums[0..2]
= 2 + 1 + 5
= 8
INITIALIZE
Build the sum of the very first window of size 3: 8.
Step 1 / 9
Approach & Solutions
Brute Force
BruteFor every possible starting index, sum the next k elements with a nested loop and keep the best total seen. Correct, but every window shares almost all of its elements with the window right before it — re-summing from scratch every time throws that overlap away.
Time
O(n·k)Space
O(1)Java
1class Solution {
2 public int maxSumSubarrayOfSizeK(int[] nums, int k) {
3 int maxSum = 0;
4 for (int i = 0; i <= nums.length - k; i++) {
5 int windowSum = 0;
6 for (int j = i; j < i + k; j++) {
7 windowSum += nums[j];
8 }
9 maxSum = Math.max(maxSum, windowSum);
10 }
11 return maxSum;
12 }
13}Optimal — Sliding Window
OptimalSum the first window of size k once. Then slide the window one step at a time: add the element entering on the right and subtract the element leaving on the left, keeping a running sum updated in O(1) per step instead of re-summing k elements every time.
Time
O(n)Space
O(1)Java
1class Solution {
2 public int maxSumSubarrayOfSizeK(int[] nums, int k) {
3 int windowSum = 0;
4 for (int i = 0; i < k; i++) {
5 windowSum += nums[i];
6 }
7 int maxSum = windowSum;
8 for (int i = k; i < nums.length; i++) {
9 windowSum += nums[i] - nums[i - k];
10 maxSum = Math.max(maxSum, windowSum);
11 }
12 return maxSum;
13 }
14}