ROD CUTTING PROBLEM - Dynamic Programming

Hey I have come up with a wonderful algorithm for solving the rod cutting problem using dynamic programming. The rod cutting algorithm as per CLRS takes O(n^2) but but but there is a suspense, in CLRS Prof. Cormen embodies the solution to only one subproblem. So I brainstormed a bit and found that if you try to find to modify the solution for both the subproblem and optimise the code a bit then you can achieve O(nlogn) .

You'll not find O(nlogn) implementation of Rod Cutting Problem anywhere on the net. Go through the code, at first it's hard to completely understand it, but if you try a bit harder you'll know what I have done. The link to problem description is given below:

https://en.wikipedia.org/wiki/Cutting_stock_problem

Here is the implementation in C:

#include<stdio.h>

#include<stdlib.h>

#define maxi(a,b) ((a) > (b) ? a : b)

int main(){

    int i,j,n,q=0;

    printf("Enter the length of the array");

    scanf("%d",&n);

    int a[n+1],r[n+1];

    a[0]=0;

    a[1]=1;

    for(i=2;i<=n;i++)

        scanf("%d",&a[i]);

    for(i=0;i<=n;i++)

        r[i]=0;

    r[1]=1;

    

    for(i=2;i<=n;i++){

        q = a[i];

        for(j=1;j<=i/2;j++)

            q = maxi(q,(r[j]+r[i-j]));

        r[i]=q;

    }

    for(i=1;i<=n;i++)

        printf("%d ",r[i]);

    return 0;

                       

}

INPUT : Enter the length of the array

10

5 8 9 10 17 17 20 24 30

OUTPUT: 1 5 8 9 10 17 18 22 25 30

If you have any doubts feel free to ask in the comments section below.