Statement

You are given a rod of length n meters. You can cut the rod into smaller pieces, and each piece has a price based on its length. Your task is to earn the maximum revenue that can be obtained by cutting up the rod into smaller pieces.

Let’s say you have a rod of length 44 meters and you have two lists: one that defines the lengths, and the other that defines the price of each length.

lengths = [1, 3, 4]

prices = [2, 7, 8]

You can cut the rod into the pieces of varying lengths and earn the following revenues:

  • Four pieces of length 11 meter =2+2+2+2=8= 2 + 2 + 2 + 2 = 8

  • One piece of length 11 meter and another piece of length 33 meters =2+7=9= 2 + 7 = 9

  • One single piece of length 44 meters =8= 8

Therefore, the maximum revenue you can generate by cutting the rod and selling the pieces is 99, by cutting the rod into two pieces, one of length 11 and the other of length 33.

Constraints:

  • 11\leq n 5000\leq5000
  • 11\leq prices[i] 106\leq10^6
  • 11\leq lengths[i] n\leq n
  • prices.length == lengths.length

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.