text: Maximum Sum Increasing Subsequence | DP | Dynamic Programming implementation of Maximum Sum Increasing Subsequence ( MSIS ) problem ; 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
code: #include <stdio.h> NEW_LINE int maxSumIS ( int arr [ ] , int n ) { int i , j , max = 0 ; int msis [ 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 ; } int main ( ) { int arr [ ] = { 1 , 101 , 2 , 3 , 100 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printf ( " Sum ▁ of ▁ maximum ▁ sum ▁ increasing ▁ " " subsequence ▁ is ▁ % d STRNEWLINE " , maxSumIS ( arr , n ) ) ; return 0 ; }