# Find the maximum sum of any continuous subarray of size K

December 23, 2020

## Introduction

You are given an array of integers with size N, and a number K. Find the maximum sum of continuous subarray of size K.

### Example

``````Input: [1, 2, 6, 2, 4, 1], k=3
Output: 12
Explanation: Subarray with maximum sum is [6, 2, 4].``````

## Solution (Brute Force)

You need to keep sum of the subarray of size=k all the time, and keep on iterating.

### Code

``````public int findMaxSum(int[] arr, int k) {
int max=0;
for (int i=0; i<=arr.length-k; i++) {
int sum_k = 0;
for (int j=i; j<i+k; j++) {
sum_k += arr[j];
}
max = Math.max(max, sum_k);
}
return max;
}``````

### Complexity

There are two loops

1. n-k times != n
2. k times

Total of O(nk)*

## Solution (Sliding Window Pattern)

If you observe problem and above solution closely,

• you need to keep continuous array
• size should be K

When you first calculate sum of the first window size of K. You already have the sum of previous window. To get the sum of next window. You need to remove first number of previous window, and add next number. So effectively you are using the sum of previous window sum. You need not to go to calculate whole sum again.

### Example

``````1 2 3 4 5

First window = 1 2 3, sum=6

For next window, subtract 1 from sum, and add 4 to remaining sum.
Second window = 2 3 4
i.e. 6 - 1 + 4 = 9``````

In this way, we are effectively moving our window from begining to end and we need to keep the max sum available till each window.

Lets look at the code.

## Code

``````public int findMaxSum(int[] arr, int k) {
int max = 0;
int left = 0;
int right = 0;

int window_sum = 0;
while (right < arr.length) {
window_sum += arr[right];
if (right >= k) {
max = Math.max(max, window_sum);

//subtract first number of previous widow
window_sum -= arr[left];

//move left pointer to next number
left ++;
}
}

return max;
}``````

We are keeping two pointers for window left and right. On completing the window size, we subtract first number of last window and keep a tab of the max sum available.

### Complexity

We are iterating over array just once. Its O(n)

## Similar Posts

### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…

System design interview is pretty common these days, specially if you are having…

### Find if Array contains Duplicate Number - Leet Code Solution

Problem Statement Given an array of integers, find if the array contains any…

### Check whether an integer number given is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

### Leetcode - Split a String Into the Max Number of Unique Substrings

Problem Statement Given a string s, return the maximum number of unique…

### Quick Sort Algorithm

This algorithm is very useful for large input. And, is quite efficient one. It…

## Latest Posts

### Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

### Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

### Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…

### Python - How to Implement Timed-Function which gets Timeout After Specified Max Timeout Value

Introduction We often require to execute in timed manner, i.e. to specify a max…

### Kubernetes - How to Set Namespace So You Do Not Need to Mention it Again and Again in Kubectl Commands.

Introduction In some of the cases, we need to specify namespace name along with…

### Kubernetes - How to Configure Docker Repository to Pull Image and Configure Secret

Introduction In most of cases, you are not pulling images from docker hub public…