Standard Bar Dynamic Programming · DP on Partition O(n*k) · O(n)
A media company slices a conveyor of ad slots into groups of at most k consecutive slots. Each group is sold at a flat rate set by its priciest slot, so every slot in the group bills at that peak price. The revenue desk wants the grouping that maximizes the total billing across the conveyor.
Input: An array arr of n integers and an integer k (max group length).
Output: Return the largest possible sum after replacing each group's values with the group maximum and summing.
1 <= len(arr) <= 5000 <= arr[i] <= 10^91 <= k <= len(arr)Input: {"arr":[1,15,7,9,2,5,10],"k":3}
Output: 84
Groups [1,15,7], [9,2,5], [10] become 15,15,15,9,10,10,10 — total 84.
Input: {"arr":[1,4,1,5,7,3,6,1,9,9,3],"k":4}
Output: 83
Optimal grouping lifts the flat-rate windows to reach 83.