Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Recomputing every window from scratch is O(n·k).
  2. 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