Maximum Average subarray of k length in C++
Maximum Average Sub-array of K length
Maximum Average Sub-array of K length in C++
On this page we will discuss about Maximum Average sub-array of k length in C++ language . We have to Find out the maximum possible average value of sub-array of K length from given sequence of N integers, a[1], a[2], , , , a[N] of N length and a integer K integer.
When working with arrays in programming, one common problem is finding patterns or optimizing values based on certain conditions. One such problem is finding the subarray of a given length k that has the maximum average value. In simple words, you are given an array of numbers, and you need to look at all possible groups of k consecutive elements, calculate their averages, and find out which group gives you the highest average.
Table of Content 📝
- Introduction
- Problem Statement: Maximum Average Subarray of k Length
- Method 1: Simple Brute Force Solution
- Algorithm
- C++ Code
- Output
- Explanation
4. Method 2: Cumulative Sum (Prefix Sum) Method
- Algorithm
- C++ Code
- Output
- Explanation
5. Method 3: Sliding Window Method (Optimized)
- Algorithm
- C++ Code
- Output
- Explanation
6. Conclusion
7. High-Level FAQs
Maximum Average Sub-array of K length in C++
In C++, maximum average subarray of k length pertains to a contiguous sub-array of length k in a given array of numbers, where the average (mean) of the k elements is the highest among all possible sub-arrays of length k in that array. In simpler words, it refers to the sub-array of k consecutive elements whose sum is the largest possible among all sub-arrays of k consecutive elements in the array, resulting in the highest average value.
For example,consider the array
[1, 12, -5, -6, 50, 3] and k=4.
The subarrays of length 4 are [1, 12, -5, -6], [12, -5, -6, 50], [-5, -6, 50, 3], and their averages are 0.5, 12.75, and 10.5 respectively. The maximum average subarray of length 4 in this case is [12, -5, -6, 50], whose average is 12.75.
Methods to solve Maximum Average Subarray problem
There are mainly three methods to solve this problem –
1. Simple Brute Force Approach
2. Cumulative Sum (Prefix Sum) Method
3. Sliding Window Method (Optimized)
Simple Brute Force Approach
Algorithm:
- Initialize max_sum to the smallest possible integer value.
- Run a loop i from 0 to n – k (to select starting index of subarray).
- For each i, run an inner loop j from i to i + k – 1 and compute the sum of these k elements.
- Compare this sum with max_sum and update max_sum if the current sum is greater.
- After all iterations, calculate max_avg = max_sum / k.
- Print the result.
Code:
#include<iostream>
#include<climits>
using namespace std;
int main() {
int arr[] = {1, 12, -5, -6, 50, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
double max_avg = INT_MIN;
for (int i = 0; i <= n - k; i++) {
int sum = 0;
for (int j = i; j < i + k; j++) { sum += arr[j]; } double avg = (double)sum / k; if (avg > max_avg) {
max_avg = avg;
}
}
cout << "Maximum average of subarray of length " << k << " is " << max_avg << endl;
return 0;
}
Output:
Maximum average of subarray of length 4 is 12.75
Explanation:
- We iterate over all possible subarrays of length k using two loops.
- The outer loop picks the starting index of the subarray.
- The inner loop calculates the sum of k consecutive elements starting from index i.
- The average of the current subarray is computed and compared with the maximum found so far.
- Finally, the maximum average is printed.
Method 2: Cumulative Sum (Prefix Sum) Method
Algorithm:
- Create a cumulative sum array csum[] of size n.
- Initialize csum[0] = arr[0]. For each i, compute csum[i] = csum[i-1] + arr[i].
- Initialize max_sum as the sum of the first k elements.
- For each index i from k to n – 1, compute the sum of subarray using csum[i] – csum[i-k].
- Compare this sum with max_sum and update if necessary.
- Finally, compute max_avg = max_sum / k.
Code:
#include<iostream>
#include<climits>
using namespace std;
int main() {
int arr[] = {1, 12, -5, -6, 50, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
int csum[n];
csum[0] = arr[0];
for (int i = 1; i < n; i++) {
csum[i] = csum[i - 1] + arr[i];
}
int max_sum = csum[k - 1];
for (int i = k; i < n; i++) { int current_sum = csum[i] - csum[i - k]; if (current_sum > max_sum) {
max_sum = current_sum;
}
}
double max_avg = (double)max_sum / k;
cout << "Maximum average of subarray of length " << k << " is " << max_avg << endl;
return 0;
}
Output:
Maximum average of subarray of length 4 is 12.75
Explanation:
- A cumulative sum array is used to store the sum of elements from index 0 to i.
- This allows us to compute the sum of any subarray in constant time.
- We first calculate the sum of the first subarray of size k.
- Then, using the cumulative sum array, we iterate through the rest of the array to check sums of all possible subarrays.
- The maximum average is calculated and printed.
Method 3: Sliding Window Method (Optimized)
Algorithm:
- Calculate the sum of the first k elements and store it in window_sum.
- Initialize max_sum as window_sum.
- Slide the window from left to right by:
- Subtracting the element that goes out of the window.
- Adding the new element coming into the window.
4. Update max_sum if window_sum is greater.
5. Finally, calculate max_avg = max_sum / k.
Code:
#include<iostream>
#include<climits>
using namespace std;
int main() {
int arr[] = {1, 12, -5, -6, 50, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
int window_sum = 0;
for (int i = 0; i < k; i++) {
window_sum += arr[i];
}
int max_sum = window_sum;
for (int i = k; i < n; i++) { window_sum += arr[i] - arr[i - k]; if (window_sum > max_sum) {
max_sum = window_sum;
}
}
double max_avg = (double)max_sum / k;
cout << "Maximum average of subarray of length " << k << " is " << max_avg << endl;
return 0;
}
Maximum average of subarray of length 4 is 12.75
Explanation:
- We first compute the sum of the first subarray of size k.
- The sliding window technique allows us to update the sum in constant time.
- For each step, we remove the leftmost element and add the next element to the window.
- We keep track of the maximum sum encountered during this process.
- Finally, we print the maximum average.
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Important Notes - Maximum Average subarray of k length in C++
- The Sliding Window method is the most efficient and recommended solution for this problem.
- The Brute Force method is good for learning purposes but not suitable for large inputs.
- The Cumulative Sum method is helpful when multiple range queries are needed.
- Understanding the Sliding Window concept is key for solving many real-world array problems.
- Always analyze the time and space complexity of your solution based on the problem size.
Final Thoughts:
In this blog, we explored three different ways to solve the Maximum Average Subarray of k Length problem in C++ – from a simple brute force method to an optimized sliding window approach.
- While the brute force method is easy to understand, it is not suitable for large datasets because of its high time complexity.
- The cumulative sum method improves performance but uses extra space.
- The sliding window technique is the most efficient solution as it provides an optimal time and space complexity.
FAQs - Maximum Average subarray of k length in C++
The sliding window technique is a method of maintaining a moving subset of elements in a collection (array or list). It allows you to update the sum, average, or other aggregate values of the window in constant time by adding the new element and removing the old one.
The sliding window method works in O(n) time complexity and uses O(1) space, making it the most efficient solution. It avoids recomputing sums for every subarray and instead updates the sum in a rolling fashion.
The brute force method uses two nested loops, resulting in a time complexity of O(n * k). This makes it inefficient for large arrays or large values of k.
The cumulative sum method uses an auxiliary array of size n, so its space complexity is O(n).
Use the cumulative sum method when you need to answer multiple range sum queries on the same array. It is more suitable when you require preprocessing to enable fast sum queries between any two arbitrary indexes.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Login/Signup to comment