740. Chunk and Max
A bakery lines up trays of loaves in a row; nums[i] is the quality score of the i-th tray. Before selling, the trays are cut into consecutive groups, each containing at most k trays (groups cannot be reordered or skipped). The baker then relabels every tray in a group with the best score found inside that group.
Return the largest possible sum of all scores after relabelling, over all ways to cut the row into groups of length at most k. Scores may be negative.
Aim for time O(n*k) and extra space O(n). If k exceeds the number of trays, groups are simply limited by the row length.
Example 1
- Input:
- nums = [3,9,2,6,1], k = 2
- Output:
- 33
- Explanation:
Groups [3], [9,2], [6,1] become 3, 9, 9, 6, 6 for a total of 33, which beats groups [3,9], [2,6], [1] at 31.
Example 2
- Input:
- nums = [4,4,4], k = 5
- Output:
- 12
- Explanation:
All trays are equal, so any grouping gives 12.
Example 3
- Input:
- nums = [-2,-8,-5,-3], k = 3
- Output:
- -9
- Explanation:
Taking [-2,-8,-5] as one group gives -2 * 3 = -6, then [-3] adds -3, total -9; better than single groups which give -18.
Constraints
1 ≤ nums.length ≤ 2 * 104
-1000 ≤ nums[i] ≤ 1000
1 ≤ k ≤ 100 (k may be larger than nums.length)
The answer fits in a 32-bit signed integer.
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 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n*k)
- Space
- O(n)