Printing Maximum Sum Increasing Subsequence | Utility function to calculate sum of all vector elements ; Function to construct Maximum Sum Increasing Subsequence ; L [ i ] - The Maximum Sum Increasing Subsequence that ends with arr [ i ] ; L [ 0 ] is equal to arr [ 0 ] ; start from index 1 ; for every j less than i ; * L [ i ] = { MaxSum ( L [ j ] ) } + arr [ i ] where j < i and arr [ j ] < arr [ i ] ; L [ i ] ends with arr [ i ] ; L [ i ] now stores Maximum Sum Increasing Subsequence of arr [ 0. . i ] that ends with arr [ i ] ; find max ; max will contain result ; Driver Code ; construct and print Max Sum IS of arr
function findSum ( arr ) { let sum = 0 ; for ( let i = 0 ; i < arr . length ; i ++ ) sum += arr [ i ] ; return sum ; } function printMaxSumIs ( arr , n ) { let L = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) L [ i ] = [ ] ; L [ 0 ] . push ( arr [ 0 ] ) ; for ( let i = 1 ; i < n ; i ++ ) { for ( let j = 0 ; j < i ; j ++ ) { if ( ( arr [ i ] > arr [ j ] ) && ( findSum ( L [ i ] ) < findSum ( L [ j ] ) ) ) { for ( let k = 0 ; k < L [ j ] . length ; k ++ ) if ( ! L [ i ] . includes ( L [ j ] [ k ] ) ) L [ i ] . push ( L [ j ] [ k ] ) ; } } L [ i ] . push ( arr [ i ] ) ; } let res = L [ 0 ] ; for ( let x = 0 ; x < L . length ; x ++ ) if ( findSum ( L [ x ] ) > findSum ( res ) ) res = L [ x ] ; for ( let i = 0 ; i < res . length ; i ++ ) document . write ( res [ i ] + " " ) ; document . write ( " " ) ; } let arr = [ 3 , 2 , 6 , 4 , 5 , 1 ] ; let n = arr . length ; printMaxSumIs ( arr , n ) ;