Maximum sum of pairs that are at least K distance apart in an array | Function to find the largest sum pair that are K distant apart ; Stores the prefix maximum array ; Base Case ; Traverse the array and update the maximum value upto index i ; Stores the maximum sum of pairs ; Iterate over the range [ K , N ] ; Find the maximum value of the sum of valid pairs ; Return the resultant sum ; Driver Code
def getMaxPairSum ( arr , N , K ) : NEW_LINE INDENT preMax = [ 0 ] * N NEW_LINE preMax [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT preMax [ i ] = max ( preMax [ i - 1 ] , arr [ i ] ) NEW_LINE DEDENT res = - 10 ** 8 NEW_LINE for i in range ( K , N ) : NEW_LINE INDENT res = max ( res , arr [ i ] + preMax [ i - K ] ) NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 4 , 8 , 6 , 3 ] NEW_LINE K = 3 NEW_LINE N = len ( arr ) NEW_LINE print ( getMaxPairSum ( arr , N , K ) ) NEW_LINE DEDENT