Rod Cutting.cpp

// { Driver Code Starts
// Initial Template for C++

#include <bits/stdc++.h>
using namespace std;


 // } Driver Code Ends
// User function Template for C++

class Solution{
  public:
    int cutRod(int price[], int n) {
        vector<vector<int>> vec(n+1);
        for(int i=0;i<=n;i++)
        vec[i] = vector<int>(n+1,0);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i<=j)
            vec[i][j] = max(price[i-1] + vec[i][j-i],vec[i-1][j]);
            else
            vec[i][j] = vec[i-1][j];
        }
        return vec[n][n];
    }
};

// { Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++) 
            cin >> a[i];
            
        Solution ob;

        cout << ob.cutRod(a, n) << endl;
    }
    return 0;
}  // } Driver Code Ends