Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: arr = [1,15,7,9,2,5,10], k = 3 Output: 84 Explanation: arr becomes [15,15,15,9,10,10,10]
Example 2:
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4 Output: 83
Example 3:
Input: arr = [1], k = 1 Output: 1
Constraints:
1 <= arr.length <= 5000 <= arr[i] <= 1091 <= k <= arr.lengthProblem Overview: You receive an integer array and a value k. You may partition the array into contiguous subarrays of length at most k. After partitioning, each subarray contributes its maximum value multiplied by its length. The goal is to maximize the total sum.
Approach 1: Recursive Approach with Memoization (Time: O(n*k), Space: O(n))
This approach models the problem as a decision at index i: choose a partition length from 1 to k, compute the maximum value inside that segment, and recursively solve the remainder of the array. While iterating possible partition sizes, maintain a running maximum so you avoid recomputing the max element each time. The contribution of a partition starting at i and ending at j becomes maxValue * (j - i + 1). Memoization stores results for each starting index so every subproblem is solved once. This converts an exponential search into an dynamic programming style solution with linear states.
Approach 2: Dynamic Programming with One-Dimensional Array (Time: O(n*k), Space: O(n))
The iterative DP approach builds the answer from left to right. Define dp[i] as the maximum sum achievable for the first i elements of the array. For each position i, look back up to k elements and treat that window as the final partition. While scanning backward from i, track the maximum element in the current window and compute the candidate value dp[i - len] + maxValue * len. Update dp[i] with the best option. This works because every optimal partitioning of the first i elements must end with a segment of size ≤ k. The algorithm only requires a single pass with a bounded backward scan, making it efficient for large arrays.
The key insight is that each partition replaces its elements with the segment maximum. Instead of explicitly constructing partitions, the algorithm only needs to track segment lengths and maximum values during iteration. This pattern frequently appears in array optimization problems and interval-based dynamic programming.
Recommended for interviews: The one-dimensional dynamic programming approach is what interviewers typically expect. It shows you can convert a recursive definition into a bottom-up DP and optimize repeated work. Starting with the recursive + memoized version demonstrates problem understanding, but implementing the iterative DP shows stronger mastery of state transitions and performance tradeoffs.
This approach uses dynamic programming with a one-dimensional array to find the solution. We use an array dp where dp[i] stores the maximum sum we can get for the array arr from the 0th index to the ith index. For each position, we try to partition the last k elements and update the dp array accordingly, keeping track of the maximum value observed in those elements to account for possible transformations.
This C program uses a dynamic programming approach with an array dp to compute the maximum sum achievable by partitioning the input array. The dp array keeps track of maximum possible sums where the loop iteratively calculates maximum sums by trying all possible partitions from 1 to k and updating dp based on the largest found values for each segment.
Time Complexity: O(n * k) since for each index, we consider up to k previous elements.
Space Complexity: O(n) for the dp array.
In this approach, a recursive function is used to solve the problem, combined with memoization to store previously computed results. The idea is to break the problem into subproblems by recursively partitioning the array from each position and recalculating sums. Alongside recursion, memoization saves time by avoiding recomputation of results for elements already processed.
In this C solution, a recursive function named helper is used to evaluate possible partitions lazily. The use of memoization, through an integer array memo, optimizes this by caching previously calculated subproblem results. This active arrangement ensures computative processes reuse stored values during recursion.
Time Complexity: O(n * k), due to exponential recursive divisions curtailed by memoization.
Space Complexity: O(n) for memoization storage.
| Approach | Complexity |
|---|---|
| Dynamic Programming with One-Dimensional Array | Time Complexity: O(n * k) since for each index, we consider up to |
| Recursive Approach with Memoization | Time Complexity: O(n * k), due to exponential recursive divisions curtailed by memoization. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n*k) | O(n) | When deriving the recurrence first or explaining the problem in interviews |
| Bottom-Up Dynamic Programming (1D DP) | O(n*k) | O(n) | General optimal solution; preferred for production and coding interviews |
DP 54. Partition Array for Maximum Sum | Front Partition 🔥 • take U forward • 143,208 views views
Watch 9 more video solutions →Practice Partition Array for Maximum Sum with our built-in code editor and test cases.
Practice on FleetCode