Back to ChallengesRod Cutting ProblemHard 30 min

Rod Cutting Problem

Given a rod of length n inches and an array of prices that includes prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Examples

Input: price = [1, 5, 8, 9, 10, 17, 17, 20], n = 8

Output: 22

Cut the rod of length 8 into two pieces of length 2 and 6. Total value = 5 + 17 = 22.

Constraints

• 1 <= n <= 1000
• price.length >= n
• 1 <= price[i] <= 10^5

Complexity Analysis

Time

O(n^2)

two nested loops over rod lengths.

Space

O(n)

array storing max values of rod parts.

Test Cases

#1 Length 8 rod

Input: [1, 5, 8, 9, 10, 17, 17, 20], 8

Expected: 22

#2 Length 8 with high price for length 1

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

Expected: 24

JavaScript

Output

Click "Run Code" to see output here...