727. Rod Seller
A carpenter owns one wooden rod of length length and can saw it into whole-unit pieces. A shop buys a piece of length j for prices[j-1] coins, so prices lists prices for lengths 1, 2, and so on up to prices.length. Longer pieces cannot be sold, but the carpenter may produce as many pieces of each sellable length as wanted.
Return the largest total revenue obtainable by cutting the rod into sellable pieces and selling them all. Cuts cost nothing, and a rod of length 0 earns 0. Pieces do not have to use the whole rod, though with non-negative prices nothing is lost by using it entirely.
Aim for time O(length * m) where m = prices.length, and space O(length).
Example 1
- Input:
- prices = [3,7,8,10], length = 9
- Output:
- 31
- Explanation:
Four pieces of length 2 and one of length 1 earn 4 * 7 + 3 = 31, better than three pieces of length 3 (24) or a piece of 4 plus others.
Example 2
- Input:
- prices = [4,1], length = 5
- Output:
- 20
- Explanation:
Only lengths 1 and 2 can be sold, so five pieces of length 1 earn 20, which beats any mix using the length-2 price of 1.
Constraints
1 ≤ prices.length ≤ 100
0 ≤ prices[i] ≤ 1000
0 ≤ length ≤ 10000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(length * m)
- Space
- O(length)