I went through the explanation on lectures and the code given by geeksforgeeks and I have a little doubt in this line :
max_val = max(max_val, price[j] +
val[i-j-1]);
In this piece of code:
/* Returns the best obtainable price for a rod of length n and
price[] as prices of different pieces */
int cutRod(int price[], int n)
{
int val[n+1];
val[0] = 0;
int i, j;
// Build the table val[] in bottom up manner and return the last entry
// from the table
for (i = 1; i<=n; i++)
{
int max_val = INT_MIN;
for (j = 0; j < i; j++)
max_val = max(max_val, price[j] + val[i-j-1]);
val[i] = max_val;
}
return val[n];
}
What I understood from the solution was that we take price of one piece and take the best of what else is left. For example :
If the length of rod is 4 then we should take max of (Price of not cutting at all,that is taking the rod of 4 as it is to get the maximum revenue, (Price of 1 ,best of 3 || Price of 2,best of 2,etc…))
So according to me the code should be :
max_val = max(Price of ith piece,Price[j]+val[i-j-1]) or something like that.
Price of not cutting at all is taken care of . Here price[] contains prices of different pieces of length i at index i-1 i.e. price[0]=price of a piece of length 1.
Outer loop evaluates val[i] for each i the maximum value for length i.
Inner loop evaluates the price we can get on cutting the rod after (j+1) length piece.
For example in case i=4
j=0 price of length 1 piece and best of length 3
j=1 price of length 2 piece and best of length 2
j=2 price of length 3 piece and best of length 1
j=3 price of length 4 piece and best of length 0
Last case checks for no cut at all. Confusion may be because of price[] array’s indexing.
What I understood from the solution was that we take price of one piece and take the best of what else is left. For example : If the length of rod is 4 then we should take max of (Price of not cutting at all,that is taking the rod of 4 as it is to get the maximum revenue, (Price of 1 ,best of 3 || Price of 2,best of 2,etc…))
Please see in the code above, lets say I have to find solution for length 4. Then subproblems I have is (0,4), (1,3), (2,2), (3,1) i.e. every (i,len-i) pair. After every iteration I am not storing the maximum value in my array but in a variable max_value. That’s why the code is written as:
max_value= max(max_value,price[j]+ val[i-j-1]);
i.e. max_value will hold the maximum of all the subproblems. After the inner loop I am finally assigning this value to val[i]. Putting price[i] is of no significance since that is the solution for the subproblem (0,len). We are concerned with all the subproblems and this one gets covered when j is 0 for every i.