Given a rod of length n inches and an array of prices P[] that contains prices of all pieces of size smaller than n. Write a program to determine the maximum revenue obtainable by cutting up the rod and selling the pieces.

Problem Note

  • You can perform these cuts in any order.
  • After a cut, the rod gets divided into two smaller sub-rods.
  • Two different sequences of cuts may give maximum revenue.

Example 1

If length of the rod and the prices of different pieces are given
Input: N = 8, P[] = [1, 5, 8, 9, 10, 17, 17, 20]

length | 1   2   3   4   5   6   7   8  
---------------------------------------
price  | 1   5   8   9  10  17  17  20

Output: 22
Explanation: The maximum obtainable revenue is 22.(By cutting the rod in two pieces of lengths 2 and 6)

Example 2

Input: N = 8, P[] = [3, 5, 8, 9, 10, 17, 17, 20]

length | 1   2   3   4   5   6   7   8 
-------------------------------------- 
price  | 3   5   8   9  10  17  17  20

Output: 24
Explanation: The maximum obtainable revenue is 24.(By cutting the rod in eight pieces of lengths 1)