Maximum sum subsequence made up of at most K distant elements including the first and last array elements | Java program for the above approach ; Pair class Store ( x , y ) Pair ; Function to find maximum sum of a subsequence satisfying the given conditions ; Stores the maximum sum ; Starting index of the subsequence ; Stores the pair of maximum value and the index of that value ; Traverse the array ; Increment the first value of deque by arr [ i ] and store it in dp [ i ] ; Delete all the values which are less than dp [ i ] in deque ; Append the current pair of value and index in deque ; If first value of the queue is at a distance > K ; Return the value at the last index ; Driver Code
import java . io . * ; import java . lang . * ; import java . util . * ; public class GFG { static class Pair { int x , y ; Pair ( int x , int y ) { this . x = x ; this . y = y ; } } private static int maxResult ( int [ ] arr , int k , int n ) { int dp [ ] = new int [ n ] ; dp [ 0 ] = arr [ 0 ] ; Deque < Pair > q = new LinkedList < Pair > ( ) ; q . add ( new Pair ( arr [ 0 ] , 0 ) ) ; for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] = arr [ i ] + q . peekFirst ( ) . x ; while ( q . size ( ) > 0 && q . peekLast ( ) . x < dp [ i ] ) q . pollLast ( ) ; q . add ( new Pair ( dp [ i ] , i ) ) ; if ( i - k == q . peekFirst ( ) . y ) q . pollFirst ( ) ; } return dp [ n - 1 ] ; } 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 ) ) ; } }