Maximum sum subsequence made up of at most K distant elements including the first and last array elements | CPP program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxResult ( int arr [ ] , int k , int n ) { int dp [ n ] = { 0 } ; dp [ 0 ] = arr [ 0 ] ; deque < pair < int , int > > q ; q . push_back ( { arr [ 0 ] , 0 } ) ; for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] = arr [ i ] + q . front ( ) . first ; while ( q . size ( ) > 0 and q . back ( ) . first < dp [ i ] ) q . pop_back ( ) ; q . push_back ( { dp [ i ] , i } ) ; if ( i - k == q . front ( ) . second ) q . pop_front ( ) ; } return dp [ n - 1 ] ; } 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 ) ; }