# Interview Questions

Ritambhara Technologies - Coding Interview Preparations > Interview Questions > Algorithms > Maximum (or minimum) sum of subarray of size k

# Maximum (or minimum) sum of subarray of size k

- February 11, 2018
- Posted by: Kamal Rawat
- Category: Algorithms

No Comments

Given an array of n integers, find the sub-array of length k with maximum sum. For example,

Input Array: {6, 4, 3, 5, 1, 9, 2} k:3 Output: 15 (sum of sub-array 5, 1, 9)

**Solution:**

The brute-force solution for this problem is to find sum of all the sub-arrays of length k, and return the maximum of all those sum.

A better solution is to use a sliding window where width of the sliding window is fixed to be of size k. There are two pointers, start and end, pointing to the first and last element of the current window. Sum of the first window is computed, and then both start and end are incremented by one position, now the sum of this window can be computed by just adding the new element and removing the outgoing element (previously start) from the previous window’s sum:

int maxSubarraySum(int *arr, int n, int k) { if(k>n){ return -1;} // IMPOSSIBLE SITUATION int maxSum = 0; for(int i=0; i<k; i++) maxSum += arr[i]; int start = 0; int end = k-1; int currentSum = maxSum; while(end<n) // MOVING THE WINDOW BY ONE POSITION { currentSum -= arr[start]; start++; end++; currentSum += arr[end]; if(currentSum > maxSum) maxSum = currentSum; } return maxSum; }

This code takes O(n) time.