Data Modelling & AI Data Structure & Algorithm

Largest sum subarray of size K containing consecutive elements

23 June 2025

0

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 elements
int 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 Code
int 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 approach
import java.util.Arrays;
 
class GFG
{
 
    // Function to find the largest sum
    // subarray such that it contains K
    // consecutive elements
public 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 Code
public 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 approach
import sys
 
# Function to find the largest sum
# subarray such that it contains K
# consecutive elements
def 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 Code
if __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 elements
function 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 Code
 
let 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:

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!

Largest sum subarray of size K containing consecutive elements

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

Here’s how some YouTube TV subscribers are claiming a $66 discount

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

How to record calls on your Samsung Galaxy phone

EDITOR PICKS

Here’s how some YouTube TV subscribers are claiming a $66 discount

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

POPULAR POSTS

Here’s how some YouTube TV subscribers are claiming a $66 discount

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

POPULAR CATEGORY

ABOUT US

FOLLOW US