Maximum sum subsequence made up of at most K distant elements including the first and last array elements

0 0 6 minutes read

Given an array arr[] consisting of N integers and an integer K, the task is to print the maximum sum possible in a subsequence satisfying the following conditions:

The elements arr[N – 1] and arr[0] are included in the subsequence.
Adjacent elements in the subsequence can be at a distance of at most K indices.

Examples:

Input: arr[] = {10, -5, -2, 4, 0, 3}, K = 3
Output: 17
Explanation:
One of possible way is as follows:
Include arr[0] into the subsequence. Sum = 10.
Include arr[3] in the subsequence. Therefore, sum = 10 + 4 = 14.
Include arr[5] in the subsequence. Therefore, total sum = 14 + 3 = 17.
Therefore, the maximum sum possible is 17.

Input: arr[] = {1, -5, -20, 4, -1, 3, -6, -3}, K = 2
Output: 0

Naive Approach: The simplest approach is to find all subsequences possible from arr[] with at most K difference between indices of adjacent elements, starting from index 0 and ending at index (N – 1). Calculate sum of all such subsequences. Finally, print the maximum of all the sums obtained.
Time Complexity: O(N*2^N)
Auxiliary Space: O(N)

Efficient Approach: The above approach can be optimized by using a Greedy Algorithm and deque. Follow the steps below to solve the problem:

Initialize an array, say dp[], to store the maximum value obtained till the current index.
Initialize a deque of pairs, say Q, to store the pair {dp[i], i}.
Assign the value of arr[0] to dp[0] and push the pair {dp[0], 0} into the deque.
Traverse the given array arr[] using the variable i and perform the following steps:
- Increment dp[i] by the sum of arr[i] and maximum value in the deque, i.e. dp[i] = arr[i] + Q[0][0].
- Traverse over the deque Q from the end and pop the last element if Q[-1][0] is less than dp[i].
- Append the pair {dp[i], i} in the deque.
- Check if the index of the first element of the deque q is equal to (i – K) or not and then, pop the first element from the deque Q.
After completing the above steps, print the value stored at the last index of dp[], i.e. dp[N – 1] as the result.

Below is the implementation of the above approach:

C++

// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to find maximum sum
// of a subsequence satisfying
// the given conditions
int maxResult(int arr[], int k, int n){
 
  // Stores the maximum sum
  int dp[n] = {0};
 
  // Starting index of
  // the subsequence
  dp[0] = arr[0];
 
  // Stores the pair of maximum value
  // and the index of that value
  deque<pair<int,int>> q;
  q.push_back({arr[0], 0});
 
  // Traverse the array
  for (int i = 1; i < n; i++)
  {
 
    // Increment the first value
    // of deque by arr[i] and
    // store it in dp[i]
    dp[i] = arr[i] + q.front().first;
 
    // Delete all the values which
    // are less than dp[i] in deque
    while (q.size() > 0 and q.back().first < dp[i])
      q.pop_back();
 
    // Append the current pair of
    // value and index in deque
    q.push_back({dp[i], i});
 
    // If first value of the
    // queue is at a distance > K
    if (i - k == q.front().second)
      q.pop_front();
  }
 
  // Return the value at the last index
  return dp[n - 1];
}
 
// Driver Code
int main()
{
  int arr[] = {10, -5, -2, 4, 0, 3};
  int K = 3;
  int n = sizeof(arr)/sizeof(arr[0]);
  cout<<maxResult(arr, K,n);
 
}
 
// This code is contributed by ipg2016107.

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class GFG {
     
    // Pair class Store (x,y) Pair
    static class Pair {
        int x, y;
 
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
    }
     
    // Function to find maximum sum
    // of a subsequence satisfying
    // the given conditions
    private static int maxResult(int[] arr, int k, int n) {
         
        // Stores the maximum sum
        int dp[] = new int[n];
         
        // Starting index of
        // the subsequence
        dp[0] = arr[0];
          
        // Stores the pair of maximum value
        // and the index of that value
        Deque<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(arr[0], 0));
          
        // Traverse the array
        for (int i = 1; i < n; i++)
        {
          
          // Increment the first value
          // of deque by arr[i] and
          // store it in dp[i]
          dp[i] = arr[i] + q.peekFirst().x;
          
          // Delete all the values which
          // are less than dp[i] in deque
          while (q.size() > 0 && q.peekLast().x < dp[i])
            q.pollLast();
          
          // Append the current pair of
          // value and index in deque
          q.add(new Pair(dp[i], i));
          
          // If first value of the
          // queue is at a distance > K
          if (i - k == q.peekFirst().y)
            q.pollFirst();
        }
          
        // Return the value at the last index
        return dp[n - 1];
         
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = {10, -5, -2, 4, 0, 3};
        int K = 3;
        int n = arr.length;
        System.out.println(maxResult(arr, K,n));
    }
     
}
 
// This code is contributed by Dheeraj Bhagchandani.

Python3

# Python program for the above approach
from collections import deque
 
# Function to find maximum sum
# of a subsequence satisfying
# the given conditions
def maxResult(arr, k):
 
    # Stores the maximum sum
    dp = [0]*len(arr)
 
    # Starting index of
    # the subsequence
    dp[0] = arr[0]
 
    # Stores the pair of maximum value
    # and the index of that value
    q = deque([(arr[0], 0)])
 
    # Traverse the array
    for i in range(1, len(arr)):
       
        # Increment the first value
        # of deque by arr[i] and
        # store it in dp[i]
        dp[i] = arr[i] + q[0][0]
 
        # Delete all the values which
        # are less than dp[i] in deque
        while q and q[-1][0] < dp[i]:
            q.pop()
 
        # Append the current pair of
        # value and index in deque
        q.append((dp[i], i))
         
        # If first value of the
        # queue is at a distance > K
        if i - k == q[0][1]:
            q.popleft()
 
    # Return the value at the last index
    return dp[-1]
 
# Driver Code
 
arr = [10, -5, -2, 4, 0, 3]
K = 3
print(maxResult(arr, K))

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.InteropServices;
 
class GFG
{
 
  class Pair {
    public int x, y;
 
    public Pair(int x, int y) {
      this.x = x;
      this.y = y;
    }
 
  }
 
  // Function to find maximum sum
  // of a subsequence satisfying
  // the given conditions
  static int maxResult(int[] arr, int k, int n) {
 
    // Stores the maximum sum
    int[] dp = new int[n];
 
    // Starting index of
    // the subsequence
    dp[0] = arr[0];
 
    // Stores the pair of maximum value
    // and the index of that value
    List<Pair> q = new List<Pair>();
 
    // Pointers to first and last element of Deque
    int l = 0, r= -1;
 
    q.Add(new Pair(arr[0], 0));
    r++;
 
    // Traverse the array
    for (int i = 1 ; i < n ; i++)
    {
 
      // Increment the first value
      // of deque by arr[i] and
      // store it in dp[i]
      dp[i] = arr[i] + q[l].x;
 
      // Delete all the values which
      // are less than dp[i] in deque
      while (l<=r && q[r].x < dp[i])
        r--;
 
      // Append the current pair of
      // value and index in deque
      if(r == q.Count - 1){
        q.Add(new Pair(dp[i], i));
      }else{
        q[r+1] = new Pair(dp[i], i);
      }
      r++;
 
      // If first value of the
      // queue is at a distance > K
      if (i - k == q[l].y)
        l++;
    }
 
    // Return the value at the last index
    return dp[n - 1];
 
  }
 
  // Driver Code
  public static void Main(string[] args){
 
    int[] arr = new int[]{10, -5, -2, 4, 0, 3};
    int K = 3;
    int n = arr.Length;
    Console.Write(maxResult(arr, K,n));
 
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

// Javascript program to implement above approach
class Pair {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}
 
// Function to find maximum sum
// of a subsequence satisfying
// the given conditions
function maxResult(arr, k, n) {
 
    // Stores the maximum sum
    let dp = new Array(n);
 
    // Starting index of
    // the subsequence
    dp[0] = arr[0];
 
    // Stores the pair of maximum value
    // and the index of that value
    let q = new Array();
 
    // Pointers to first and last element of Deque
    let l = 0, r = -1;
 
    q.push(new Pair(arr[0], 0));
    r++;
 
    // Traverse the array
    for (let i = 1; i < n; i++) {
 
        // Increment the first value
        // of deque by arr[i] and
        // store it in dp[i]
        dp[i] = arr[i] + q[l].x;
 
        // Delete all the values which
        // are less than dp[i] in deque
        while (l <= r && q[r].x < dp[i])
            r--;
 
        // Append the current pair of
        // value and index in deque
        if (r == q.length - 1) {
            q.push(new Pair(dp[i], i));
        } else {
            q[r + 1] = new Pair(dp[i], i);
        }
        r++;
 
        // If first value of the
        // queue is at a distance > K
        if (i - k == q[l].y)
            l++;
    }
 
    // Return the value at the last index
    return dp[n - 1];
 
}
 
// Driver Code
let arr = [10, -5, -2, 4, 0, 3];
let K = 3;
let n = arr.length;
console.log(maxResult(arr, K, n));
 
// This code is contributed by Saurabh Jaiswal

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

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 zambiatek!