{"post":"

Problem: The problem statement is quite simple to understand. The input contains an unsorted array with multiple elements in it. The output is the maximum current sum of the k consecutive elements.

Input: {1,9,5,6,4,7}, k=2

Output: 14

There are two approaches to solve it:

Brute Force Approach: Use nested loops to calculate the current sum of the consecutive elements.
Optimized Approach: Use a single loop to reduce the time complexity for the same.

# Brute Force Algorithm:

Input the array size, window size and the array elements.
If the array size is greater than the window size, then call the function to find the maximum sum.
Use the first loop to iterate the k-sized loop to find the window sum and after each complete iteration of the second loop (window sized loop) check for the max sum.
Finally, print the maximum sum value with its window size.

Code:

#include<iostream>\r\n#include<bits/stdc++.h>\r\nusing namespace std;\nvoid ms(int a[], int n, int k){
\nint i, j, cur, maxsum = INT_MIN;
\nfor (i = 0; i <= n - k; i++){\r\ncur = 0;\r\nfor (j = 0; j < k; j++){
\n  cur = cur + a[i + j];\r\n\r\n}\r\n\r\nmaxsum = max(cur, maxsum);\n
\n}
\ncout << \"Maximum sum of \" << k << \" consecutive elements is: \" << maxsum;
\n}
\nint main(){\r\nint len, k, i;
\ncout << \"Enter the number of elements : \" << endl;
\ncin >> len;
\ncout << \"Enter the window size : \" << endl;
\ncin >> k;
\nint array[len];
\ncout << \"Enter the array elements : \" << endl;
\nfor (i = 0; i < len; i++){
\ncin &gt;&gt; array[i];\n
\n}
\ncout << \"Original array is: \" << endl;
\nfor (i = 0; i < len; i++){
\ncout &lt;&lt; array[i] &lt;&lt; \" \";\n
\n}
\ncout << endl;
\nif (len < k){
\ncout &lt;&lt; \"Window size is larger than array size\" &lt;&lt; endl;\n
\n} else {
\nms(array, len, k);\n
\n}
\nreturn 0;
\n}

Output:

Enter the number of elements:\n8 \nEnter the window size: \n2 \nEnter the array elements: \n1 \n-3 \n9 \n-5 \n-2 \n6 \n4 \n-7 \nOriginal array is: \n1 -3 9 -5 -2 6 4 -7 \n

Maximum sum of 2 consecutive elements is: 14

Time Complexity: O(k*n)

# Optimized Algorithm(Sliding Window)

Input the array size, window size and the array elements.
If the array size is greater than the window size, then call the function to find the maximum sum.
Find the sum of first k consecutive elements of the array and then store in a variable which is the window sum.
Now iterate through rest of the elements from k till the last element in the array by adding one element and eliminating the first element.
Compare the sum and store the maximum sum value in a separate variable.
After completing the iteration, print the maximum sum value with its window size.

Code:

#include<bits/stdc++.h>\r\nusing namespace std;\nvoid ms(int a[], int n, int k){
\nint i, j, maxsum = 0;
\nfor (i = 0; i < k; i++){\r\nmaxsum = maxsum + a[i];\r\n}
\nint wsum = maxsum;
\nfor (i = k; i < n; i++){\r\nwsum = wsum + a[i] - a[i - k];\r\nmaxsum = max(maxsum, wsum);\r\n}
\ncout << \"Maximum sum of \" << k << \" consecutive elements is: \" << maxsum;\r\n}
\nint main(){\r\nint len, k, i;\r\ncout << \"Enter the number of elements : \" << endl;\r\ncin >> len;\r\ncout << \"Enter the window size : \" << endl;\r\ncin >> k;\r\nint array[len];\r\ncout << \"Enter the array elements : \" << endl;\r\nfor (i = 0; i < len; i++){\r\ncin >> array[i];\r\n}
\ncout << \"Original array is: \" << endl;
\nfor (i = 0; i < len; i++){\r\ncout << array[i] << \" \";\r\n}
\ncout << endl;
\nif (len < k){\r\ncout << \"Window size is larger than array size\" << endl;\r\n} else {\r\nms(array, len, k);\r\n}
\nreturn 0;
\n}

Output:

Enter the number of elements:\n8 \nEnter the window size: \n2 \nEnter the array elements: \n1 \n-3 \n9 \n-5 \n-2 \n6 \n4 \n-7 \nOriginal array is: \n1 -3 9 -5 -2 6 4 -7 \n

Maximum sum of 2 consecutive elements is: 14

Time Complexity: O(n)

This way with more practises of data structures and algorithms we can approach towards efficient source codes of any particular programs.

\n","title":"Maximum of all subarrays of size k (Sliding Window Technique)","authorDetails":{"name":"Ankita Khan","slug":"ankita-khan"},"seo":{"title":"Maximum of all subarrays of size k (Sliding Window Technique)"},"description":"We will find the maximum sum of all subarrays of size k using the sliding window technique.","slug":"sliding-window-technique/","articleId":"636a83417bb1ce5072622b3a","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}