Maximum subsequence sum possible by multiplying each element by its index | Java program for the above approach ; Initialize dp array ; Function to find the maximum sum of the subsequence formed ; Base Case ; If already calculated state occurs ; Include the current element ; Exclude the current element ; Update the maximum ans ; Function to calculate maximum sum of the subsequence obtained ; Initialise the dp array with - 1 ; Print the maximum sum possible ; Driver Code ; Given array ; Size of the array ; Function Call
import java . util . * ; class GFG { static int [ ] [ ] dp = new int [ 1005 ] [ 1005 ] ; static int maximumSumUtil ( int a [ ] , int index , int count , int n ) { if ( index > n count > n + 1 ) { return 0 ; } if ( dp [ index ] [ count ] != - 1 ) return dp [ index ] [ count ] ; int ans1 = maximumSumUtil ( a , index + 1 , count + 1 , n ) + a [ index ] * count ; int ans2 = maximumSumUtil ( a , index + 1 , count , n ) ; return ( dp [ index ] [ count ] = Math . max ( ans1 , ans2 ) ) ; } static void maximumSum ( int arr [ ] , int N ) { for ( int i = 0 ; i < 1005 ; i ++ ) { for ( int j = 0 ; j < 1005 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } System . out . print ( maximumSumUtil ( arr , 0 , 1 , N - 1 ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { - 1 , 2 , - 10 , 4 , - 20 } ; int N = arr . length ; maximumSum ( arr , N ) ; } }