Consider an array of size **N** and given a size **K** we need to find maximum elements of all subarrays of size **K** in this array of size **N**.

This is best followed by an example

```
3 4 6 3 4
#For subarray size of 2, the subarrays are
[3, 4], [4, 6], [6, 3], [3,4]
#Thus the maximum values are
4 6 6 4
```

## Naive Solution

A simple solution is the best starting point. We know how to find the maximum element in an array. So we just need to loop over all the sub-arrays and find the maximum element over each of these subarrays.

```
void printMaxK(int arr[], int size, int sub_arr_size) {
for (int i = 0; i < size - k; i += 1) {
int max = arr[i];
for (int j = i + 1; j < i + k; j+= 1) {
if (max < arr[j])
max = arr[j];
}
cout<<max<<" ";
}
}
```

This solution works but can be improved upon. For each of the subarrays, we’re comparing **sub_arr_size – 1** elements each time when we don’t really need to.

**Consider** the example we used earlier

```
3 4 6 3 4
#For subarray size of 3
# 1. comparing 3 4 6 gives 6
# 2. comparing 4 6 3 gives 6
# 3. comparing 6 3 4 gives 6
```

The number of comparisons done seems unnecessary since for each subarray we loose one element and add another, thus the rest of the elements need not be compared at all , **well not always**. And this is what we can exploit to speed things up.

We can easily use **Memoization however** we don’t need to save all results.

**As long as the** maximum value found in the earlier subarray **is part of the new subarray** we just need to compare the **item being added** with this maximum value. **Thereby** we reduce our comparisons from variable to ** just 1**.

**However**, if the largest element found earlier **is not part **of the new subarray**, since we keep moving forward** we need to find out the maximum value using the naive solution **but only for the **subarray.

## Optimized Solution

```
void printMaxK(int arr[], int n, int k){
/*
* We solve the first problem of K elements
* of the contiguous sub-array.
*
* There are two things possible now, when we move
* to the next K elements, either the largest element
* is also part of the next K elements or not.
*
* If it's the first case we only need to check that
* largest element with the one we're adding now.
* otherwise we'll have to figure out the new largest
* element.
* This is more of a memoization problem.
*/
int curr_max = arr[0];
int curr_idx = 0;
for(int j = 1; j < k; j += 1) {
if (arr[j] > curr_max) {
curr_max = arr[j];
curr_idx = j;
}
}
cout<<curr_max<<" ";
//We now slide our window over the next subarray.
//You can consider this to be a sliding window
//where we slide it to the right leaving out
//one element while adding exactly one element.
for(int i = 1; i < n - k + 1 ; i += 1) {
//If the max of previous subarray is part of
//this subarray.
if (curr_idx >= i) {
//Check only the element added.
if (arr[i + k - 1] > curr_max) {
curr_idx = i + k - 1;
curr_max = arr[curr_idx];
}
} else {
//We need to find a new maximum
//by going over this subarray.
curr_max = arr[i];
curr_idx = i;
for (int j = i + 1; j < i + k; j += 1) {
if (curr_max < arr[j]) {
curr_idx = j;
curr_max = arr[curr_idx];
}
}
}
printf("%d", curr_max);
}
printf("\n");
}
```