Maximize the Sum of a Subsequence from an Array based on given conditions | Java program to implement the above approach ; Function to select the array elements to maximize the sum of the selected elements ; If the entire array is solved ; Memoized subproblem ; Calculate sum considering the current element in the subsequence ; Calculate sum without considering the current element in the subsequence ; Update the maximum of the above sums in the dp [ ] [ ] table ; Driver Code ; Initialize the dp array ; Function call
import java . util . * ; public class GFG { public static int maximumSum ( int [ ] a , int count , int index , int n , int [ ] [ ] dp ) { if ( index == n ) return 0 ; if ( dp [ index ] [ count ] != - 1 ) return dp [ index ] [ count ] ; int take_element = a [ index ] * count + maximumSum ( a , count + 1 , index + 1 , n , dp ) ; int dont_take = maximumSum ( a , count , index + 1 , n , dp ) ; return dp [ index ] [ count ] = Math . max ( take_element , dont_take ) ; } public static void main ( String args [ ] ) { int n = 5 ; int a [ ] = { - 1 , - 9 , 0 , 5 , - 7 } ; int dp [ ] [ ] = new int [ n + 1 ] [ n + 1 ] ; for ( int i [ ] : dp ) Arrays . fill ( i , - 1 ) ; System . out . println ( maximumSum ( a , 1 , 0 , n , dp ) ) ; } }