Maximum Sum Subsequence of length k | Python program to calculate the maximum sum of increasing subsequence of length k ; In the implementation dp [ n ] [ k ] represents maximum sum subsequence of length k and the subsequence is ending at index n . ; Initializing whole multidimensional dp array with value - 1 ; For each ith position increasing subsequence of length 1 is equal to that array ith value so initializing dp [ i ] [ 1 ] with that array value ; Starting from 1 st index as we have calculated for 0 th index . Computing optimized dp values in bottom - up manner ; check for increasing subsequence ; Proceed if value is pre calculated ; Check for all the subsequences ending at any j < i and try including element at index i in them for some length l . Update the maximum value for every length . ; The final result would be the maximum value of dp [ i ] [ k ] for all different i . ; When no subsequence of length k is possible sum would be considered zero ; Driver Code
def MaxIncreasingSub ( arr , n , k ) : NEW_LINE INDENT dp = [ - 1 ] * n NEW_LINE ans = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT dp [ i ] = [ - 1 ] * ( k + 1 ) NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT dp [ i ] [ 1 ] = arr [ i ] NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if arr [ j ] < arr [ i ] : NEW_LINE INDENT for l in range ( 1 , k ) : NEW_LINE INDENT if dp [ j ] [ l ] != - 1 : NEW_LINE INDENT dp [ i ] [ l + 1 ] = max ( dp [ i ] [ l + 1 ] , dp [ j ] [ l ] + arr [ i ] ) NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ans < dp [ i ] [ k ] : NEW_LINE INDENT ans = dp [ i ] [ k ] NEW_LINE DEDENT DEDENT return ( 0 if ans == - 1 else ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n , k = 8 , 3 NEW_LINE arr = [ 8 , 5 , 9 , 10 , 5 , 6 , 21 , 8 ] NEW_LINE ans = MaxIncreasingSub ( arr , n , k ) NEW_LINE print ( ans ) NEW_LINE DEDENT