Given a rod of length n and a price array where price[i] is the value of a rod piece of length i+1, return the maximum obtainable value by cutting and selling the rod pieces. Pieces can be used repeatedly, making this an unbounded knapsack maximization problem.
prices = value of pieces of length 1..n, n = rod length
maximum value obtainable by cutting and selling the rod
Example 1:
Input:
prices = [1,5,8,9,10,17,17,20] n = 8
Output:
22
Explanation:
The maximum revenue for length 8 is 22.
Example 2:
Input:
prices = [2,5,7,8] n = 4
Output:
10
Explanation:
Cut the rod into two pieces of length 2 for value 5 + 5 = 10.