Maximum subsequence sum possible by multiplying each element by its index | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 1005 ] [ 1005 ] ; 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 ] = max ( ans1 , ans2 ) ) ; } int maximumSum ( int arr [ ] , int N ) { memset ( dp , -1 , sizeof ( dp ) ) ; cout << maximumSumUtil ( arr , 0 , 1 , N - 1 ) ; } int main ( ) { int arr [ ] = { -1 , 2 , -10 , 4 , -20 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; maximumSum ( arr , N ) ; return 0 ; }