You are given an integer N, which represents the length of a rod, and an array
of integers, which represents the prices of rod pieces of length varying from 1
to N.
You have to find the maximum value that can be obtained by selling the rod.
You can sell it in pieces or as a whole.
Say the input array is [1, 5, 8, 9, 10, 17, 17, 20] of size 8 and a rod of length 8.
The above figure shows that a piece of rod of length 1 has a price 1, a piece of rod of
length 2 has a price 5, a piece of rod of length 3 has a price 8, and so on.
Hence some of the ways of selling the rod are:
1-1-1-1-1-1-1-1
2-2-2-2
2-3-3
Approach
What
There are 2 strategies for making trees for this problem. 1. CUT STRATEGY :
We make a dp array of the length 9 as shown in figure 2.
The marked cell denotes the maximum price possible by cutting a rod of
length 5 and the original array on top denotes the original prices.
Since the smallest problem is at length 0, therefore we start solving from
there and move up to the length 8.
We know that for length 0 the maximum price possible is 0.
Also, according to the given array of numbers, for length 1, the maximum
price is 1.
See in figure 2, we have tweaked our original array such that it is of length 9
such that for length 1, the index is 1 instead of index 0 and further for the rest
of the elements.
A rod of length 2 can be cut as 1-1 or simply remain as 2. The prices for them
are 1+1=2 and 5 respectively. We have to choose the maximum selling price,
which is why we store 5 against the length 2.
Now, we move to length 3.
Figure 3 shows that there are 3 ways possible for a length 3.
We can directly sell the rod of 3 length for price 8.
We can sell the rod of length 1 for the original price 1 and the other cut
piece of length 2, for its maximum price 5.
Similarly, we can sell the rod of length 2 for the original price 5 and the
other cut piece of length 1, for its maximum price 1.
Out of the 3 cases, the maximum selling price is 8.
For a rod of length 4, the ways are denoted in figure 4.
From this we find out the maximum possible way 2-2 which is equal to 10.
We want you to solve the rest of the dp on your own and check your result
with figure 5.
From Figure 5, we get the answer that for the rod of length 8, the maximum
selling price is 22.
If you face any difficulties in solving this dp array you can also watch the solution
video.
We summarize all the trees till length 6 in figure shown.
Here, the numbers along the edge denote the price from the original array and the
numbers at the vertices marked with star denote the optimized dp array price.
2. LEFT-RIGHT STRATEGY :
Another way of making trees for rod cutting is given in figure shown below.
For n=2, we cut the rod into two halves of length 1 each. Hence, the left half
of the rod interacts with the right half as a Cartesian product.
So, one of the ways for n=2 is obtained by adding 1 to the previous result of
n=1 and the other way is the original price of 2 itself.
Similarly, for n=3, half of 3 is 1. Hence, the rod is cut into 1*2. Since the result
for n=1 and n=2 interact with each other, we get the number of ways for n=3
as shown in the figure.
For n=3, it is enough to write 1*2. The result of 2*1 is not required because it
will give the same answer as 1*2.
Also, one of the ways is the original price of 3 itself.
For n=4, we cut the left half of 1 as well as of 2. When 1 is the left half then the
rod is cut as 1*3 and when 2 is the left half the rod is cut as 2*2. The result
obtained by these 2 interactions is given in the figure.
The same process is followed for the rest of the lengths too.
In case you face any difficulties in this problem, we suggest you watch the
solution video.
We now discuss the method of filling the dp array using left-right strategy.
The storage, meaning and direction is the same as it was in the cut strategy.
For a rod of length 0 and 1, the number of ways are 0 and 1 respectively.
Now, for length 2, there are 2 ways :
We have an option of selecting the best price for length 1 added to itself
versus the best price of length 2. Hence out of price 2 and 5, we select 2.
This method is followed by all the other lengths and is shown in figure 9.
Out of all the prices in figure 10, the maximum price is 22. Hence, it is our
final answer.
In case you have any difficulties in understanding the dp array for this
strategy, we suggest you watch the solution video .
Code
We write the code of this program using the left-right strategy.
We want you to write it yourself first and then refer to the code given below.
import java.io.*;
import java.util.*;
public class Main {
public static int solution(int[] prices) {
int[]np=new int[prices.length+1];
for(int i=0;i< prices.length;i++){
np[i+1]=prices[i];
}
int[]dp=new int[np.length];
dp[0]=0;
dp[1]=np[1];
for(int i=2;i< dp.length;i++){
dp[i]=np[i];
int li=1;
int ri=i-1;
while(li<=ri){
if(dp[li]+dp[ri]>dp[i]){
dp[i]=dp[li]+dp[ri];
}
li++;
ri--;
}
}
return dp[dp.length-1];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
prices[i] = scn.nextInt();
}
System.out.println(solution(prices));
}
}
java;
true";
Analysis
Time Complexity O(n)
Space Complexity O(1)
With this we conclude our discussion. We hope you were able to understand it
clearly.
If you still have any doubts you can just watch its solution video.
