Maximum subsequence sum possible by multiplying each element by its index | Let 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 ; Letialise the dp array with - 1 ; Prlet the maximum sum possible ; Given array ; Size of the array ; Function Call
let dp = new Array ( 1005 ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } function maximumSumUtil ( a , index , count , n ) { if ( index > n count > n + 1 ) { return 0 ; } if ( dp [ index ] [ count ] != - 1 ) return dp [ index ] [ count ] ; let ans1 = maximumSumUtil ( a , index + 1 , count + 1 , n ) + a [ index ] * count ; let ans2 = maximumSumUtil ( a , index + 1 , count , n ) ; return ( dp [ index ] [ count ] = Math . max ( ans1 , ans2 ) ) ; } function maximumSum ( arr , N ) { for ( let i = 0 ; i < 1005 ; i ++ ) { for ( let j = 0 ; j < 1005 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } document . write ( maximumSumUtil ( arr , 0 , 1 , N - 1 ) ) ; } let arr = [ - 1 , 2 , - 10 , 4 , - 20 ] ; let N = arr . length ; maximumSum ( arr , N ) ;