Given an array arr[] consisting of N positive integers and a positive integer K, the task is to find the maximum sum of the subarray of size K such that it contains K consecutive elements in any combination.
Examples:
Input: arr[] = {10, 12, 9, 8, 10, 15, 1, 3, 2}, K = 3
Output: 27
Explanation:
The subarray having K (= 3) consecutive elements is {9, 8, 10} whose sum of elements is 9 + 8 + 10 = 27, which is maximum.Input: arr[] = {7, 20, 2, 3, 4}, K = 2
Output: 7
Approach: The given problem can be solved by checking every subarray of size K whether it contains consecutive elements or not and then maximize the sum of the subarray accordingly. Follow the steps below to solve the problem:
- Initialize a variable, say currSum to store the sum of the current subarray of K elements if the elements are consecutive.
- Initialize a variable maxSum that stores the maximum resultant sum of any subarray of size K.
- Iterate over the range [0, N – K] using the variable i and perform the following steps:
- Store the K elements starting from i in an array V[].
- Sort the array V[] in increasing order.
- Traverse the array V[] to check if all the elements are consecutive or not. If found to be true, then store the sum of the current subarray in currSum and update the maxSum to the maximum of maxSum and currSum.
- After completing the above steps, print the value of maxSum as the result.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the largest sum// subarray such that it contains K// consecutive elementsint maximumSum(vector<int> A, int N, int K){ // Stores sum of subarray having // K consecutive elements int curr_sum = 0; // Stores the maximum sum among all // subarrays of size K having // consecutive elements int max_sum = INT_MIN; // Traverse the array for (int i = 0; i < N - K + 1; i++) { // Store K elements of one // subarray at a time vector<int> dupl_arr( A.begin() + i, A.begin() + i + K); // Sort the duplicate array // in ascending order sort(dupl_arr.begin(), dupl_arr.end()); // Checks if elements in subarray // are consecutive or not bool flag = true; // Traverse the k elements for (int j = 1; j < K; j++) { // If not consecutive, break if (dupl_arr[j] - dupl_arr[j - 1] != 1) { flag = false; break; } } // If flag is true update the // maximum sum if (flag) { int temp = 0; // Stores the sum of elements // of the current subarray curr_sum = accumulate( dupl_arr.begin(), dupl_arr.end(), temp); // Update the max_sum max_sum = max(max_sum, curr_sum); // Reset curr_sum curr_sum = 0; } } // Return the result return max_sum;}// Driver Codeint main(){ vector<int> arr = { 10, 12, 9, 8, 10, 15, 1, 3, 2 }; int K = 3; int N = arr.size(); cout << maximumSum(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;class GFG{ // Function to find the largest sum // subarray such that it contains K // consecutive elementspublic static Integer maximumSum(int[] A, int N, int K){ // Stores sum of subarray having // K consecutive elements int curr_sum = 0; // Stores the maximum sum among all // subarrays of size K having // consecutive elements int max_sum = Integer.MIN_VALUE; // Traverse the array for (int i = 0; i < N - K + 1; i++) { // Store K elements of one // subarray at a time int[] dupl_arr = Arrays.copyOfRange(A, i, i + K); // Sort the duplicate array // in ascending order Arrays.sort(dupl_arr); // Checks if elements in subarray // are consecutive or not Boolean flag = true; // Traverse the k elements for (int j = 1; j < K; j++) { // If not consecutive, break if (dupl_arr[j] - dupl_arr[j - 1] != 1) { flag = false; break; } } // If flag is true update the // maximum sum if (flag) { int temp = 0; // Stores the sum of elements // of the current subarray curr_sum = 0; for(int x = 0; x < dupl_arr.length; x++){ curr_sum += dupl_arr[x]; } // Update the max_sum max_sum = Math.max(max_sum, curr_sum); // Reset curr_sum curr_sum = 0; } } // Return the result return max_sum;} // Driver Codepublic static void main(String args[]) { int[] arr = { 10, 12, 9, 8, 10, 15, 1, 3, 2 }; int K = 3; int N = arr.length; System.out.println(maximumSum(arr, N, K)); }}// This code is contributed by _saurabh_jaiswal. |
Python3
# Python3 program for the above approachimport sys# Function to find the largest sum# subarray such that it contains K# consecutive elementsdef maximumSum(A, N, K): # Stores sum of subarray having # K consecutive elements curr_sum = 0 # Stores the maximum sum among all # subarrays of size K having # consecutive elements max_sum = -sys.maxsize - 1 # Traverse the array for i in range(N - K + 1): # Store K elements of one # subarray at a time dupl_arr = A[i:i + K] # Sort the duplicate array # in ascending order dupl_arr.sort() # Checks if elements in subarray # are consecutive or not flag = True # Traverse the k elements for j in range(1, K, 1): # If not consecutive, break if (dupl_arr[j] - dupl_arr[j - 1] != 1): flag = False break # If flag is true update the # maximum sum if (flag): temp = 0 # Stores the sum of elements # of the current subarray curr_sum = temp curr_sum = sum(dupl_arr) # Update the max_sum max_sum = max(max_sum, curr_sum) # Reset curr_sum curr_sum = 0 # Return the result return max_sum# Driver Codeif __name__ == '__main__': arr = [ 10, 12, 9, 8, 10, 15, 1, 3, 2 ] K = 3 N = len(arr) print(maximumSum(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR |
C#
using System;public class GFG { // Function to find the largest sum // subarray such that it contains K // consecutive elements public static int maximumSum(int[] A, int N, int K) { // Stores sum of subarray having // K consecutive elements int curr_sum = 0; // Stores the maximum sum among all // subarrays of size K having // consecutive elements int max_sum = int.MinValue; // Traverse the array for (int i = 0; i < N - K + 1; i++) { // Store K elements of one // subarray at a time int[] dupl_arr = new int[K]; Array.Copy(A, i, dupl_arr, 0, K); // Sort the duplicate array // in ascending order Array.Sort(dupl_arr); // Checks if elements in subarray // are consecutive or not bool flag = true; // Traverse the k elements for (int j = 1; j < K; j++) { // If not consecutive, break if (dupl_arr[j] - dupl_arr[j - 1] != 1) { flag = false; break; } } // If flag is true update the // maximum sum if (flag) { // Stores the sum of elements // of the current subarray curr_sum = 0; for (int x = 0; x < dupl_arr.Length; x++) { curr_sum += dupl_arr[x]; } // Update the max_sum max_sum = Math.Max(max_sum,curr_sum); // Reset curr_sum curr_sum = 0; } } // Return the result return max_sum; } // Driver Code public static void Main() { int[] arr = { 10, 12, 9, 8, 10, 15, 1, 3, 2 }; int K = 3; int N = arr.Length; Console.WriteLine(maximumSum(arr, N, K)); }} |
Javascript
<script>// JavaScript program for the above approach// Function to find the largest sum// subarray such that it contains K// consecutive elementsfunction maximumSum(A, N, K) { // Stores sum of subarray having // K consecutive elements let curr_sum = 0; // Stores the maximum sum among all // subarrays of size K having // consecutive elements let max_sum = Number.MIN_SAFE_INTEGER; // Traverse the array for (let i = 0; i < N - K + 1; i++) { // Store K elements of one // subarray at a time let dupl_arr = [...A.slice(i, i + K)]; // Sort the duplicate array // in ascending order dupl_arr.sort((a, b) => a - b) // Checks if elements in subarray // are consecutive or not let flag = true; // Traverse the k elements for (let j = 1; j < K; j++) { // If not consecutive, break if (dupl_arr[j] - dupl_arr[j - 1] != 1) { flag = false; break; } } // If flag is true update the // maximum sum if (flag) { let temp = 0; // Stores the sum of elements // of the current subarray curr_sum = dupl_arr.reduce((acc, cur) => acc + cur, 0) // Update the max_sum max_sum = Math.max(max_sum, curr_sum); // Reset curr_sum curr_sum = 0; } } // Return the result return max_sum;}// Driver Codelet arr = [10, 12, 9, 8, 10, 15, 1, 3, 2];let K = 3;let N = arr.length;document.write(maximumSum(arr, N, K));</script> |
Output:
27
Time Complexity: O(N*K*log K)
Auxiliary Space: O(K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
