Rod Cutting

PROBLEM :

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Input:
First line consists of T test cases. First line of every test case consists of N, denoting the size of array. Second line of every test case consists of price of ith length piece.

Output:
Single line output consists of maximum price obtained.

Constraints:
1<=T<=100
1<=N<=100
1<=Ai<=100

Example:
Input:
1
8
1 5 8 9 10 17 17 20

Output:
22

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<limits.h>
int RodCutting(int [],int ) ;
int maxof(int a,int ) ;
int main()
{
int t ;
cin>>t ;
while(t--){
   int no ;
   cin>>no ;
 
   int arr[no] ;
   for(int i=0;i<no;i++)
       cin>>arr[i] ;
     
   cout<<RodCutting(arr,no)<<endl ;
}
return 0;
}

int RodCutting(int arr[],int no){
    int dp[no+1] ;
    dp[0]=0 ;
   
    for(int i=1;i<=no;i++){
        int max=INT_MIN ;
        for(int j=0;j<i;j++)
            max=maxof(max,arr[j]+dp[i-j-1]) ;
        dp[i]=max ;
    }
    return dp[no] ;
}

int maxof(int a,int b){
    return a>b?a:b ;
}

--------------------------------------------------------------------------------