- Given a rod of length n inches along with an array {pi}1isn, in which pi denotes the price for a rod (piece) of length i inches. The goal is to cut the given rod of length n into smaller pieces (or do nothing) so that the total price of the pieces is maximized. \begin{tabular}{|rc|} \hline EXTENDED-BOTTOM-UP-CUT-RoD (p,n) \\ 1 & let r[0n] and s[0n] be new arrays \\ 2 & r[0]=0 \\ 3 & for j=1 to n \\ 4 & q= \\ 5 & for i=1 to j \\ 6 & if q