Maximum Sum Subsequence of length k | C ++ 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 function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MaxIncreasingSub ( int arr [ ] , int n , int k ) { int dp [ n ] [ k + 1 ] , ans = -1 ; memset ( dp , -1 , sizeof ( dp ) ) ; for ( int i = 0 ; i < n ; i ++ ) { dp [ i ] [ 1 ] = arr [ i ] ; } for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( arr [ j ] < arr [ i ] ) { for ( int l = 1 ; l <= k - 1 ; l ++ ) { if ( dp [ j ] [ l ] != -1 ) { dp [ i ] [ l + 1 ] = max ( dp [ i ] [ l + 1 ] , dp [ j ] [ l ] + arr [ i ] ) ; } } } } } for ( int i = 0 ; i < n ; i ++ ) { if ( ans < dp [ i ] [ k ] ) ans = dp [ i ] [ k ] ; } return ( ans == -1 ) ? 0 : ans ; } int main ( ) { int n = 8 , k = 3 ; int arr [ n ] = { 8 , 5 , 9 , 10 , 5 , 6 , 21 , 8 } ; int ans = MaxIncreasingSub ( arr , n , k ) ; cout << ans << " STRNEWLINE " ; return 0 ; }