Rod Segment Profit Maximiser
Problem Description
You are given a rod of integer length `rodLen` and a price list `priceList` where `priceList[i]` is the price of a rod segment of length `i + 1` (1-indexed lengths).
You may cut the rod into any number of pieces (each of integer length) and sell each piece at its listed price. Return the **maximum total revenue** obtainable.
**Example 1:**
```
Input: rodLen = 4, priceList = [2, 5, 7, 8]
Output: 10
```
**Explanation:** Cut into two pieces of length 2 each (price 5 + 5 = 10). Selling as a whole piece of length 4 gives only 8.
**Example 2:**
```
Input: rodLen = 7, priceList = [1, 5, 8, 9, 10, 17, 17]
Output: 18
```
**Explanation:** Cut into pieces of length 1 and 6 (price 1 + 17 = 18), or two pieces of length 3 (price 8 + 8 = 16 — worse). Optimal is length 6 + length 1 = 18.
Constraints
- 1 <= rodLen <= 1000
- priceList.length == rodLen
- 1 <= priceList[i] <= 10000
Follow-up
Can you also reconstruct the actual sequence of cuts that achieves the maximum revenue?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.