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*2N)
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 conditionsint 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 Codeint 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 approachimport 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 approachfrom collections import deque# Function to find maximum sum# of a subsequence satisfying# the given conditionsdef 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 Codearr = [10, -5, -2, 4, 0, 3]K = 3print(maxResult(arr, K)) |
C#
// C# program to implement above approachusing 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 approachclass Pair { constructor(x, y) { this.x = x; this.y = y; }}// Function to find maximum sum// of a subsequence satisfying// the given conditionsfunction 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 Codelet 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:
17
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
