Maximum sum increasing subsequence from a prefix and a given element after prefix is must | Javascript program to find maximum sum increasing subsequence tiint i - th index and including k - th index . ; Initializing the first row of the dp [ ] [ ] . ; Creating the dp [ ] [ ] matrix . ; To calculate for i = 4 and k = 6. ; Driver code
function pre_compute ( a , n , index , k ) { let dp = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i < n ; i ++ ) { if ( a [ i ] > a [ 0 ] ) dp [ 0 ] [ i ] = a [ i ] + a [ 0 ] ; else dp [ 0 ] [ i ] = a [ i ] ; } for ( let i = 1 ; i < n ; i ++ ) { for ( let j = 0 ; j < n ; j ++ ) { if ( a [ j ] > a [ i ] && j > i ) { if ( dp [ i - 1 ] [ i ] + a [ j ] > dp [ i - 1 ] [ j ] ) dp [ i ] [ j ] = dp [ i - 1 ] [ i ] + a [ j ] ; else dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; } else dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; } } return dp [ index ] [ k ] ; } let a = [ 1 , 101 , 2 , 3 , 100 , 4 , 5 ] ; let n = a . length ; let index = 4 , k = 6 ; document . write ( pre_compute ( a , n , index , k ) ) ;