DSA interview question

Partition Array for Maximum Sum

Medium · Algorithms · Topics: dynamic programming, partition

The problem

You're working on a video editing tool's "scene smoothing" feature. The product team noticed that raw brightness readings frame-by-frame look jarring when played back — viewers want each short cluster of frames to feel "smoothed" so the overall visual energy is maximized for highlight reels. The rule: you can group up to k consecutive frames together, and once grouped, every frame in that group gets replaced by the maximum brightness value in that group. You want to choose how to partition the entire frame sequence into such groups (each of length at most k) so that the total sum of the resulting (smoothed) array is as large as possible.

Given an integer array arr and an integer k, partition the array into contiguous subarrays of length at most k. After partitioning, each subarray's values are replaced by the maximum value of that subarray. Return the largest possible sum of the array after partitioning.

Function signature

int maxSumAfterPartitioning(vector<int>& arr, int k);

Test cases

Input `arr`	`k`	Output	Explanation
`[1,15,7,9,2,5,10]`	3	84	Partition: `[1,15,7]→15,15,15`, `[9,2]→9,9`, `[5,10]→10,10` → 15+15+15+9+9+10+10 = 84
`[1,4,1,5,7,3,6,1,9,9,3]`	4	83	Optimal grouping yields sum 83
`[1]`	1	1	Single element, trivially itself
`[1,4,1,5,7,3,6,1,9,9,3]`	1	49	k=1 means no smoothing happens — sum of original array
`[5,5,5,5]`	4	20	Whole array as one group, max is 5, 4×5 = 20

(Constraints typically: 1 <= arr.length <= 500, 0 <= arr[i] <= 109, 1 <= k <= arr.length)

How interviewers phrase it

"You're given an array and a window size limit k. You can break the array into chunks of size at most k. Each chunk gets 'flattened' to its max value. Maximize the total sum."
Sometimes phrased visually: "Imagine smoothing a histogram in blocks of size up to k, where each block becomes flat at its peak height — maximize area."
This is LeetCode 1043, a classic "partition DP" problem — interviewers may not name it but the phrasing "partition into subarrays" is the giveaway.

Clarifying questions to ask

Does "at most k" mean every partition can be any length from 1 to k, not necessarily exactly k? (Yes — this is key, it's not a fixed-size sliding window.)
Can arr contain negative numbers? (If so, the greedy "always pick max group size" intuition can break — confirm constraints. Typically arr[i] ≥ 0 here.)
What's the array size — is O(n·k) acceptable, or do we need something smarter? (For n ≤ 500, O(n·k) is fully fine.)
Should I return just the max sum, or also reconstruct the actual partitioning? (Usually just the sum, but be ready for the follow-up.)

Follow-ups to expect

"Can you do this with O(1) extra space (in-place)?"
"Can you reconstruct the actual partition boundaries, not just the sum?"
"What if k could be very large (close to n) — does complexity change?"
"What if negative numbers are allowed?"
"Can you do this greedily without DP?"
"What's a brute force, and why is it exponential?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview