Data Modelling & AI Data Structure & Algorithm

Maximum subsequence sum such that no K elements are consecutive

23 June 2025

0

Given an array arr[] of N positive integers, the task is to find the maximum sum of a subsequence consisting of no K consecutive array elements.

Examples:

Input: arr[] = {10, 5, 8, 16, 21}, K = 4
Output: 55
Explanation:
Maximum sum is obtained by picking 10, 8, 16, 21.

Input: arr[] = {4, 12, 22, 18, 34, 12, 25}, K = 5
Output: 111
Explanation:
Maximum sum is obtained by picking 12, 22, 18, 34, 25

Naive Approach: The simplest approach is to generate all the subsets of the given array and for each subset, check if it contains K consecutive array elements or not. For subsets found to be not containing K consecutive array elements, calculate their sum. Find the maximum of the sums of all such subsequences.

Time Complexity: O(N*2^N)
Auxiliary Space: O(1)

Efficient Approach: There are many overlapping subproblems in the above solution which are calculated again and again. To avoid recomputation of the same subproblems, the idea is to use Memoization or Tabulation. Follow the steps below to solve the problem:

Initialize an array dp[] to memorize the maximum value of the sum up to each index.
Now, dp[i] gives the maximum value of the sum that can be picked such that no K elements are consecutive from the 0^th Index till i^thindex.
The base case is when i < K :
- Since the array elements are all positive, pick all the elements before (K )^th Index.
- So dp[1] = arr [0] and dp[i] = dp[i -1] + arr[i-1], (1 ≤ i < k ).
Now for i ≥ K :
- Since K consecutive elements cannot be picked, so skip at least one element from i to (i – K + 1) inclusive so to make sure that no K elements are consecutive.
- Since any element can contribute to the result, so skip every element from i to (i – K + 1) inclusive and will keep track of the maximum sum.
  - To skip the j^th Element, add maximum sum till (j – 1)^th Index which is given by dp[j – 1] with the sum of all the elements from (j + 1)^th index to i^th index which can be calculated in O(1) time using prefix array sum.
- Therefore update the current dp state as: dp[i] = max (dp[i], dp[j -1] + prefix[i] – prefix [j]), (i ≤ j ≤ (i – K + 1)), where prefix array stores the prefix sum.
Print the maximum sum after the above steps.

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 maximum sum
// of a subsequence consisting of
// no K consecutive array elements
int Max_Sum(int arr[], int K, int N)
{
   
    // Stores states of dp
    int dp[N + 1];
 
    // Initialise dp state
    memset(dp, 0, sizeof(dp));
 
    // Stores the prefix sum
    int prefix[N + 1];
 
    prefix[0] = 0;
 
    // Update the prefix sum
    for(int i = 1; i <= N; i++)
    {
        prefix[i] = prefix[i - 1] + arr[i-1];
    }
 
    // Base case for i < K
    dp[0] = 0;
 
    // For indices less than k
    // take all the elements
    for(int i = 1; i < K ; i++)
    {
        dp[i] = prefix[i];
    }
 
    // For i >= K  case
    for(int i = K ; i <= N; ++i)
    {
       
        // Skip each element from i to
        // (i - K + 1) to ensure that
        // no K elements are consecutive
        for(int j = i; j >= (i - K + 1); j--) 
        {
           
            // j-th element is skipped
 
            // Update the current dp state
            dp[i] = max(dp[i], dp[j - 1] + 
                    prefix[i] - prefix[j]);
        }
    }
 
    // dp[N] stores the maximum sum
    return dp[N];
}
 
// Driver Code
int main()
{
   
    // Given array arr[]
    int arr[] = { 4, 12, 22, 18, 34, 12, 25 };
 
    int N = sizeof(arr) / sizeof(int);
    int K = 5;
 
    // Function Call
    cout << Max_Sum(arr, K, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to find the maximum sum
// of a subsequence consisting of
// no K consecutive array elements
public static int Max_Sum(int[] arr, int K,
                          int N)
{
     
    // Stores states of dp
    int[] dp = new int[N + 1];
 
    // Initialise dp state
    Arrays.fill(dp, 0);
 
    // Stores the prefix sum
    int[] prefix = new int[N + 1];
 
    prefix[0] = 0;
 
    // Update the prefix sum
    for(int i = 1; i <= N; i++) 
    {
        prefix[i] = prefix[i - 1] + arr[i-1];
    }
 
    // Base case for i < K
    dp[0] = 0;
 
    // For indices less than k
    // take all the elements
    for(int i = 1; i <= K - 1; i++) 
    {
        dp[i] = prefix[i];
    }
 
    // For i >= K  case
    for(int i = K ; i <= N; ++i)
    {
         
        // Skip each element from i to
        // (i - K + 1) to ensure that
        // no K elements are consecutive
        for(int j = i; j >= (i - K + 1); j--)
        {
             
            // j-th element is skipped
 
            // Update the current dp state
            dp[i] = Math.max(dp[i], dp[j - 1] + 
                         prefix[i] - prefix[j]);
        }
    }
 
    // dp[N] stores the maximum sum
    return dp[N];
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int[] arr = { 4, 12, 22, 18, 34, 12, 25 };
 
    int N = arr.length;
    int K = 5;
 
    // Function Call
    System.out.println(Max_Sum(arr, K, N));
}
}
 
// This code is contributed by akhilsaini

Python3

# Python3 program for the above approach
 
# Function to find the maximum sum
# of a subsequence consisting of
# no K consecutive array elements
def Max_Sum(arr, K, N):
     
    # Stores states of dp
    dp = [0] * (N + 1)
     
    # Stores the prefix sum
    prefix = [None] * (N + 1)
     
    prefix[0] = 0
     
    # Update the prefix sum
    for i in range(1, N + 1):
        prefix[i] = prefix[i - 1] + arr[i - 1]
       
    # Base case for i < K
    dp[0] = 0
     
    # For indices less than k
    # take all the elements
    for i in range(1, K):
        dp[i] = prefix[i]
     
    # For i >= K case
    for i in range(K, N + 1):
         
        # Skip each element from i to
        # (i - K + 1) to ensure that
        # no K elements are consecutive
        for j in range(i, i - K, -1):
             
            # j-th element is skipped
             
            # Update the current dp state
            dp[i] = max(dp[i], dp[j - 1] +
                    prefix[i] - prefix[j])
     
    # dp[N] stores the maximum sum
    return dp[N]
 
# Driver Code
if __name__ == "__main__":
     
    # Given array arr[]
    arr = [ 4, 12, 22, 18, 34, 12, 25 ]
     
    N = len(arr)
    K = 5
     
    # Function call
    print(Max_Sum(arr, K, N))
     
# This code is contributed by akhilsaini

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the maximum sum
// of a subsequence consisting of
// no K consecutive array elements
static int Max_Sum(int[] arr, int K, int N)
{
     
    // Stores states of dp
    int[] dp = new int[N + 1];
 
    // Initialise dp state
    Array.Fill(dp, 0);
 
    // Stores the prefix sum
    int[] prefix = new int[N + 1];
 
    prefix[0] = 0;
 
    // Update the prefix sum
    for(int i = 1; i <= N; i++) 
    {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
 
    // Base case for i < K
    dp[0] = 0;
 
    // For indices less than k 
    // take all the elements
    for(int i = 1; i <= K - 1; i++)
    {
        dp[i] = prefix[i];
    }
 
    // For i >= K case
    for(int i = K; i <= N; ++i) 
    {
         
        // Skip each element from i to
        // (i - K + 1) to ensure that
        // no K elements are consecutive
        for(int j = i; j >= (i - K + 1); j--) 
        {
             
            // j-th element is skipped
 
            // Update the current dp state
            dp[i] = Math.Max(dp[i], dp[j - 1] +
                         prefix[i] - prefix[j]);
        }
    }
 
    // dp[N] stores the maximum sum
    return dp[N];
}
 
// Driver Code
static public void Main()
{
     
    // Given array arr[]
    int[] arr = { 4, 12, 22, 18, 34, 12, 25 };
 
    int N = arr.Length;
    int K = 5;
 
    // Function Call
    Console.WriteLine(Max_Sum(arr, K, N));
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the maximum sum
// of a subsequence consisting of
// no K consecutive array elements
function Max_Sum(arr, K, N)
{
   
    // Stores states of dp
    var dp = Array(N+1).fill(0);
 
    // Stores the prefix sum
    var prefix = Array(N+1);
 
    prefix[0] = 0;
 
    // Update the prefix sum
    for(var i = 1; i <= N; i++)
    {
        prefix[i] = prefix[i - 1] + arr[i-1];
    }
 
    // Base case for i < K
    dp[0] = 0;
 
    // For indices less than k
    // take all the elements
    for(var i = 1; i < K ; i++)
    {
        dp[i] = prefix[i];
    }
 
    // For i >= K  case
    for(var i = K ; i <= N; ++i)
    {
       
        // Skip each element from i to
        // (i - K + 1) to ensure that
        // no K elements are consecutive
        for(var j = i; j >= (i - K + 1); j--) 
        {
           
            // j-th element is skipped
 
            // Update the current dp state
            dp[i] = Math.max(dp[i], dp[j - 1] + 
                    prefix[i] - prefix[j]);
        }
    }
 
    // dp[N] stores the maximum sum
    return dp[N];
}
 
// Driver Code
 
// Given array arr[]
var arr = [4, 12, 22, 18, 34, 12, 25];
var N = arr.length;
var K = 5;
 
// Function Call
document.write( Max_Sum(arr, K, N));
 
</script>

Output:

Time Complexity: O(N*K) where N is the number of elements in the array and K is the input such that no K elements are consecutive.
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

4 COMMENTS

Uuodiyala 6 December 2025 At 6:02 pm

… [Trackback]

[…] Information to that Topic: geeksforgeeks.org/maximum-subsequence-sum-such-that-no-k-elements-are-consecutive/ […]

Log in to leave a comment
bitcoin today 7 December 2025 At 11:56 am

… [Trackback]

[…] Find More on to that Topic: geeksforgeeks.org/maximum-subsequence-sum-such-that-no-k-elements-are-consecutive/ […]

Log in to leave a comment
purchase dmt extraction kit Siegen, 12 May 2026 At 6:17 am

… [Trackback]

[…] Read More Information here on that Topic: geeksforgeeks.org/maximum-subsequence-sum-such-that-no-k-elements-are-consecutive/ […]

Log in to leave a comment
joycasino kz 9 July 2026 At 8:45 pm

… [Trackback]

[…] Here you will find 1630 additional Info to that Topic: geeksforgeeks.org/maximum-subsequence-sum-such-that-no-k-elements-are-consecutive/ […]

Log in to leave a comment

Maximum subsequence sum such that no K elements are consecutive

C++

Java

Python3

C#

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

4 COMMENTS

LEAVE A REPLY Cancel reply

Most Popular

The phone that made it all possible. [Video]

Google Health’s latest update closes another Fitbit gap

Google Earth Pro users get hit with bad news as the desktop app is being retired

Opinion: With iOS 26 over the horizon, jailbreaking iPhones is officially a thing of the past

EDITOR PICKS

The phone that made it all possible. [Video]

Google Health’s latest update closes another Fitbit gap

Google Earth Pro users get hit with bad news as the desktop app is being retired

POPULAR POSTS

The phone that made it all possible. [Video]

Google Health’s latest update closes another Fitbit gap

Google Earth Pro users get hit with bad news as the desktop app is being retired

POPULAR CATEGORY

ABOUT US

FOLLOW US