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");
}