Maximum Sum Increasing Subsequence | DP | maxSumIS ( ) returns the maximum sum of increasing subsequence in arr [ ] of size n ; Initialize msis values for all indexes ; Compute maximum sum values in bottom up manner ; Pick maximum of all msis values ; Driver Code
function maxSumIS ( arr , n ) { let i , j , max = 0 ; let msis = new Array ( n ) ; for ( i = 0 ; i < n ; i ++ ) msis [ i ] = arr [ i ] ; for ( i = 1 ; i < n ; i ++ ) for ( j = 0 ; j < i ; j ++ ) if ( arr [ i ] > arr [ j ] && msis [ i ] < msis [ j ] + arr [ i ] ) msis [ i ] = msis [ j ] + arr [ i ] ; for ( i = 0 ; i < n ; i ++ ) if ( max < msis [ i ] ) max = msis [ i ] ; return max ; } let arr = [ 1 , 101 , 2 , 3 , 100 , 4 , 5 ] ; let n = arr . length ; document . write ( " " + " " + maxSumIS ( arr , n ) ) ;