Maximize the Sum of a Subsequence from an Array based on given conditions | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 6 ; int maximumSum ( int a [ ] , int count , int index , int n , int dp [ N ] [ N ] ) { 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 ] = max ( take_element , dont_take ) ; } int main ( ) { int n = 5 ; int a [ ] = { -1 , -9 , 0 , 5 , -7 } ; int dp [ N ] [ N ] ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << ( maximumSum ( a , 1 , 0 , n , dp ) ) ; }