Rod Cutting
MediumP3Coding
A rod has length n = prices.length. prices[i] is the selling price of a piece of length i + 1. You may cut the rod into pieces of integer lengths (or not cut it at all) and sell every piece.
Return the maximum total price.
Example 1
- Input
- prices = [1,5,8,9,10,17,17,20]
- Output
- 22
- Why
- Cut into pieces of length 2 and 6: 5 + 17 = 22.
Example 2
- Input
- prices = [3,5,8,9,10,17,17,20]
- Output
- 24
Example 3
- Input
- prices = [2]
- Output
- 2
Constraints
- 1 <= prices.length <= 1000
- 0 <= prices[i] <= 10^4
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.