Maximize Sum possible from an Array by the given moves | C ++ program to implement the above approach ; Function to find the maximum sum possible by given moves from the array ; Checking for boundary ; If previously computed subproblem occurs ; If element can be moved left ; Calculate maximum possible sum by moving left from current index ; If element can be moved right ; Calculate maximum possible sum by moving right from current index and update the maximum sum ; Store the maximum sum ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int k = 1 ; const int m = 4 ; int maxValue ( int a [ ] , int n , int pos , int moves , int left , int dp [ ] [ k + 1 ] ) { if ( moves == 0 || ( pos > n - 1 pos < 0 ) ) return 0 ; if ( dp [ pos ] [ left ] != -1 ) return dp [ pos ] [ left ] ; int value = 0 ; if ( left > 0 && pos >= 1 ) value = max ( value , a [ pos ] + maxValue ( a , n , pos - 1 , moves - 1 , left - 1 , dp ) ) ; if ( pos <= n - 1 ) value = max ( value , a [ pos ] + maxValue ( a , n , pos + 1 , moves - 1 , left , dp ) ) ; return dp [ pos ] [ left ] = value ; } int main ( ) { int n = 5 ; int a [ ] = { 1 , 5 , 4 , 3 , 2 } ; int dp [ n + 1 ] [ k + 1 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << ( a [ 0 ] + maxValue ( a , n , 1 , m , k , dp ) ) << endl ; }