Practice › Sliding Window
Maximum Sum Subarray of Size K
Easy · Sliding Window · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Find the maximum sum of any contiguous subarray of exactly k elements.
Input
First line: n. Second line: n integers. Third line: k.
Output
The maximum window sum.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
- -10^4 ≤ a[i] ≤ 10^4
Slide the window: add the new element, subtract the one that leaves — O(n).
Example 1
Input
6 2 1 5 1 3 2 3
Output
9
Example 2
Input
3 -1 -2 -3 1
Output
-1
Hints
- Recomputing every window from scratch is O(n·k).
- When the window slides one step, add the element entering and subtract the element leaving.
Approach
Sum the first k elements. Then for i = k … n−1, update sum += a[i] − a[i − k] and keep the maximum. Start the maximum at the first window's sum, not 0, because every value could be negative.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
cin >> k;
long long sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
long long best = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i - k];
best = max(best, sum);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
window = best = sum(a[:k])
for i in range(k, n):
window += a[i] - a[i - k]
best = max(best, window)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int k = sc.nextInt();
long sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
long best = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i - k];
best = Math.max(best, sum);
}
System.out.println(best);
}
}Solve Maximum Sum Subarray of Size K online · All practice problems