Maximum sum subsequence made up of at most K distant elements including the first and last array elements | Python 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
from collections import deque NEW_LINE / * Pair class Store ( x , y ) Pair * / NEW_LINE def maxResult ( arr , k ) : NEW_LINE INDENT dp = [ 0 ] * len ( arr ) NEW_LINE dp [ 0 ] = arr [ 0 ] NEW_LINE q = deque ( [ ( arr [ 0 ] , 0 ) ] ) NEW_LINE for i in range ( 1 , len ( arr ) ) : NEW_LINE INDENT dp [ i ] = arr [ i ] + q [ 0 ] [ 0 ] NEW_LINE while q and q [ - 1 ] [ 0 ] < dp [ i ] : NEW_LINE INDENT q . pop ( ) NEW_LINE DEDENT q . append ( ( dp [ i ] , i ) ) NEW_LINE if i - k == q [ 0 ] [ 1 ] : NEW_LINE INDENT q . popleft ( ) NEW_LINE DEDENT DEDENT return dp [ - 1 ] NEW_LINE DEDENT arr = [ 10 , - 5 , - 2 , 4 , 0 , 3 ] NEW_LINE K = 3 NEW_LINE print ( maxResult ( arr , K ) ) NEW_LINE