Printing Maximum Sum Increasing Subsequence | Dynamic Programming solution to construct 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
import java . util . * ; class GFG { static int findSum ( Vector < Integer > arr ) { int sum = 0 ; for ( int i : arr ) sum += i ; return sum ; } static void printMaxSumIs ( int [ ] arr , int n ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] L = new Vector [ n ] ; for ( int i = 0 ; i < n ; i ++ ) L [ i ] = new Vector < > ( ) ; L [ 0 ] . add ( arr [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ i ] > arr [ j ] ) && ( findSum ( L [ i ] ) < findSum ( L [ j ] ) ) ) { for ( int k : L [ j ] ) if ( ! L [ i ] . contains ( k ) ) L [ i ] . add ( k ) ; } } L [ i ] . add ( arr [ i ] ) ; } Vector < Integer > res = new Vector < > ( L [ 0 ] ) ; for ( Vector < Integer > x : L ) if ( findSum ( x ) > findSum ( res ) ) res = x ; for ( int i : res ) System . out . print ( i + " ▁ " ) ; System . out . println ( ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 3 , 2 , 6 , 4 , 5 , 1 } ; int n = arr . length ; printMaxSumIs ( arr , n ) ; } }