Question: You are given a rod of length 'L' and an array of prices where price at each index is the price obtained by selling rod of length equal to that index. You need to find the maximum price, you can get by selling pieces of rod.

Note: Rod can be sold in as many pieces of integer length as you want. You may also sell the rod as a whole if that gets you maximum price.

Example: Lets say, there is rod of length 8 units with price array given below:

[0, 3, 7, 8, 9, 12, 13, 19, 20]

We have put 0 at 0th index to show price of length 0.

For this particular example, maximum selling price will be 28 by cutting the rod in 4 pieces of length 2.


Answer: How will you approach this problem?

Since we can cut the rod in pieces of any integer length, then we can start by thinking in a top-down fashion. First we will cut the rod in 2 pieces, which have maximum price of themselves. The cut should be in such a position that addition of prices for these 2 pieces obtain maximum selling price. Now we have to find the maximum prices of these 2 pieces by taking a piece at a time.

In this process, these 2 pieces can be of length L (original length of rod) and ZERO as well. Now we will repeat the process for these 2 pieces as well recursively until we get pieces of length 1 or ZERO.

find_maximum_price(L) = MAX(
                        for x in 0..L
                        find_maximum_price(x) + find_maximum_price(L-x)
                        )

But if we notice, there will be a lot of similar problem in order to solve all the problems for different length pieces of the rod. If we go bottom up, solve smaller problems first and save results for them, we can avoid solving same problem again and again. As many of you may get it by now, this is simple Dynamic Programming problem now. Where you solve for smaller problems, memoize results and solve actual problem using these results.

Code:
Below is the ruby code for the same. The logic is very simple. First iterate the rod length from 0 to L and save maximum selling price for each sub part in the result array. Once your result array is filled, return value for of result array for length L.

# @param [Array<Fixnum>] price Price array for rod
# @return [Fixnum] maximum selling price
def find_maximum_price(price)
  # initialize result array as 0 for price of rod length 0
  maxprice = [0]

  for i in 1..(price.length-1)
      maxprice[i] = price[i]
    for j in 0..i
      p = maxprice[j] + maxprice[i-j]
      if p > maxprice[i]
        maxprice[i] = p
      end
    end
  end
  return maxprice[-1] # return maxprice for length L
end

price = [0, 3, 7, 8, 9, 12, 17, 17, 20]  # input price array
puts "maximum price obtained = #{find_maximum_price(price)}"

Complexity: As we can see there are 2 loops, outer loop from 0 to L and intter from 0 to outer-loop-index. So the run time complexity is O(n2).

We can also find the length of rod pieces to obtain maximum selling price. I am leaving that part to readers.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.