Standard Bar Dynamic Programming · DP on Subsequences O(N^2) · O(N)
A supplier receives one continuous spool of cable N meters long. Predefined retail bundles exist for every integer length, each with its own price, and the spool can be sliced into any combination of bundle lengths. Sales wants the cutting plan that maximizes revenue from the single spool.
Input: An integer N (spool length) and an array price of N integers where price[i] is the revenue for a bundle of length i+1.
Output: Return the maximum revenue obtainable by slicing the spool into bundles of integer lengths.
1 <= N <= 10001 <= price[i] <= 10^5Input: {"N":8,"price":[1,5,8,9,10,17,17,20]}
Output: 22
Cut into lengths 2 and 6: 5 + 17 = 22.
Input: {"N":8,"price":[3,5,8,9,10,17,17,20]}
Output: 24
Eight 1-meter bundles fetch 8 * 3 = 24, beating every other partition.