Partition Array for Maximum Sum solution and explanation
Google
9 more videos on this problem
DP 54. Partition Array for Maximum Sum | Front Partition 🔥take U forward · 21:39 · 154K views
Partition Array for Maximum Sum - Leetcode 1043 - PythonNeetCodeIO · 27:33 · 22K views
Partition Array for Maximum Sum | Why DP | Recursion | Memo | Bottom Up | Leetcode 1043codestorywithMIK · 28:21 · 14K views
LeetCode 1043. Partition Array for Maximum Sum Explanation and Solutionhappygirlzt · 8:10 · 11K views
1043. Partition Array for Maximum Sum | DP | Recursion - Top Down - Bottom Up - Bottom Up OptimisedAryan Mittal · 25:35 · 5K views
1043. Partition Array for Maximum Sum (Leetcode Medium)Programming Live with Larry · 11:19 · 1K views
Leetcode 1043. Partition Array for Maximum SumElite Code · 39:12 · 1K views
LeetCode - 1043. Partition Array for Maximum Sum | Dynamic Programming | JavaOrkhan Gasanov · 20:09 · 211 views
LeetCode 1043. Partition Array for Maximum Sum | Java | DPHow we live in Texas · 14:23 · 165 views
LeetCode 1043 - Partition Array for Maximum Sum - PythonAlpha-Code · 11:04 · 140 views
The problem
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.length
Approach overview
Problem 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.
Approach 1: Dynamic Programming with One-Dimensional Array
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.
def maxSumAfterPartitioning(arr, k):
n = len(arr)
dp = [0] * (n + 1)
for i in range(1, n + 1):
maxElem, maxSum = 0, 0
for j in range(1, min(k, i) + 1):
maxElem = max(maxElem, arr[i-j])
maxSum = max(maxSum, dp[i-j] + maxElem * j)
dp[i] = maxSum
return dp[n]
arr = [1, 15, 7, 9, 2, 5, 10]
k = 3
print(maxSumAfterPartitioning(arr, k))import java.util.Arrays;
class Solution {
public int maxSumAfterPartitioning(int[] arr, int k) {
int n = arr.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, 0);
for (int i = 1; i <= n; i++) {
int maxElem = 0, maxSum = 0;
for (int j = 1; j <= k && i-j >= 0; j++) {
maxElem = Math.max(maxElem, arr[i-j]);
maxSum = Math.max(maxSum, dp[i-j] + maxElem * j);
}
dp[i] = maxSum;
}
return dp[n];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 15, 7, 9, 2, 5, 10};
int k = 3;
System.out.println(sol.maxSumAfterPartitioning(arr, k));
}
}#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = arr.size();
vector<int> dp(n+1, 0);
for (int i = 1; i <= n; i++) {
int maxElem = 0, maxSum = 0;
for (int j = 1; j <= k && i-j >= 0; j++) {
maxElem = max(maxElem, arr[i-j]);
maxSum = max(maxSum, dp[i-j] + maxElem * j);
}
dp[i] = maxSum;
}
return dp[n];
}
};
int main() {
Solution sol;
vector<int> arr = {1, 15, 7, 9, 2, 5, 10};
int k = 3;
cout << sol.maxSumAfterPartitioning(arr, k) << endl;
return 0;
}function maxSumAfterPartitioning(arr, k) {
const n = arr.length;
const dp = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
let maxElem = 0, maxSum = 0;
for (let j = 1; j <= k && i-j >= 0; j++) {
maxElem = Math.max(maxElem, arr[i-j]);
maxSum = Math.max(maxSum, dp[i-j] + maxElem * j);
}
dp[i] = maxSum;
}
return dp[n];
}
const arr = [1, 15, 7, 9, 2, 5, 10];
const k = 3;
console.log(maxSumAfterPartitioning(arr, k));#include <stdio.h>
#include <string.h>
int maxSumAfterPartitioning(int* arr, int arrSize, int k) {
int dp[arrSize+1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= arrSize; i++) {
int maxElem = 0, maxSum = 0;
for (int j = 1; j <= k && i-j >= 0; j++) {
maxElem = (arr[i-j] > maxElem) ? arr[i-j] : maxElem;
maxSum = (dp[i-j] + maxElem * j > maxSum) ? dp[i-j] + maxElem * j : maxSum;
}
dp[i] = maxSum;
}
return dp[arrSize];
}
int main() {
int arr[] = {1, 15, 7, 9, 2, 5, 10};
int k = 3;
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxSumAfterPartitioning(arr, arrSize, k));
return 0;
}using System;
public class Solution {
public int MaxSumAfterPartitioning(int[] arr, int k) {
int n = arr.Length;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int maxElem = 0, maxSum = 0;
for (int j = 1; j <= k && i-j >= 0; j++) {
maxElem = Math.Max(maxElem, arr[i-j]);
maxSum = Math.Max(maxSum, dp[i-j] + maxElem * j);
}
dp[i] = maxSum;
}
return dp[n];
}
public static void Main(string[] args) {
var sol = new Solution();
int[] arr = {1, 15, 7, 9, 2, 5, 10};
int k = 3;
Console.WriteLine(sol.MaxSumAfterPartitioning(arr, k));
}
}This Python function operates using a dynamic programming approach encapsulated in a list named dp. It records the maximum sum feasible by iteratively determining the best partitions up to length k. During each iteration, potential partitions are evaluated, and the maximum combination is persisted in the dp array.
Time Complexity: O(n * k) because of the nested loop structure per index.
Space Complexity: O(n) for the list maintaining subtotals.
Approach 2: Recursive Approach with Memoization
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.
def maxSumAfterPartitioning(arr, k):
def helper(i):
if i == len(arr):
return 0
if memo[i] != -1:
return memo[i]
maxElem, maxSum = 0, 0
for j in range(i, min(i + k, len(arr))):
maxElem = max(maxElem, arr[j])
maxSum = max(maxSum, maxElem * (j-i+1) + helper(j+1))
memo[i] = maxSum
return maxSum
memo = [-1] * len(arr)
return helper(0)
arr = [1, 15, 7, 9, 2, 5, 10]
k = 3
print(maxSumAfterPartitioning(arr, k))import java.util.Arrays;
class Solution {
private int helper(int[] arr, int n, int k, int[] memo, int i) {
if (i >= n) return 0;
if (memo[i] != -1) return memo[i];
int maxElem = 0, maxSum = 0;
for (int j = i; j < i + k && j < n; j++) {
maxElem = Math.max(maxElem, arr[j]);
maxSum = Math.max(maxSum, maxElem * (j-i+1) + helper(arr, n, k, memo, j+1));
}
return memo[i] = maxSum;
}
public int maxSumAfterPartitioning(int[] arr, int k) {
int n = arr.length;
int[] memo = new int[n];
Arrays.fill(memo, -1);
return helper(arr, n, k, memo, 0);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 15, 7, 9, 2, 5, 10};
int k = 3;
System.out.println(sol.maxSumAfterPartitioning(arr, k));
}
}#include <vector>
#include <iostream>
#include <climits>
#include <cstring>
using namespace std;
class Solution {
public:
int helper(vector<int>& arr, int n, int k, vector<int>& memo, int i) {
if (i >= n) return 0;
if (memo[i] != -1) return memo[i];
int maxElem = INT_MIN, maxSum = 0;
for (int j = i; j < i + k && j < n; ++j) {
maxElem = max(maxElem, arr[j]);
maxSum = max(maxSum, maxElem * (j-i+1) + helper(arr, n, k, memo, j+1));
}
return memo[i] = maxSum;
}
int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = arr.size();
vector<int> memo(n, -1);
return helper(arr, n, k, memo, 0);
}
};
int main() {
Solution sol;
vector<int> arr = {1, 15, 7, 9, 2, 5, 10};
int k = 3;
cout << sol.maxSumAfterPartitioning(arr, k) << endl;
return 0;
}function maxSumAfterPartitioning(arr, k) {
function helper(i) {
if (i >= arr.length) return 0;
if (memo[i] !== -1) return memo[i];
let maxElem = 0, maxSum = 0;
for (let j = i; j < Math.min(arr.length, i + k); j++) {
maxElem = Math.max(maxElem, arr[j]);
maxSum = Math.max(maxSum, maxElem * (j - i + 1) + helper(j + 1));
}
memo[i] = maxSum;
return maxSum;
}
const memo = new Array(arr.length).fill(-1);
return helper(0);
}
const arr = [1, 15, 7, 9, 2, 5, 10];
const k = 3;
console.log(maxSumAfterPartitioning(arr, k));#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>
int max(int a, int b) {
return a > b ? a : b;
}
int helper(int* arr, int n, int k, int* memo, int i) {
if (i >= n) return 0;
if (memo[i] != -1) return memo[i];
int maxElem = INT_MIN, maxSum = 0;
for (int j = i; j < i + k && j < n; ++j) {
maxElem = max(maxElem, arr[j]);
maxSum = max(maxSum, maxElem * (j-i+1) + helper(arr, n, k, memo, j+1));
}
return memo[i] = maxSum;
}
int maxSumAfterPartitioning(int* arr, int arrSize, int k) {
int* memo = (int*)malloc(arrSize * sizeof(int));
memset(memo, -1, arrSize * sizeof(int));
return helper(arr, arrSize, k, memo, 0);
}
int main() {
int arr[] = {1, 15, 7, 9, 2, 5, 10};
int k = 3;
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxSumAfterPartitioning(arr, arrSize, k));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private int Helper(int[] arr, int n, int k, int[] memo, int i) {
if (i >= n) return 0;
if (memo[i] != -1) return memo[i];
int maxElem = 0, maxSum = 0;
for (int j = i; j < i + k && j < n; j++) {
maxElem = Math.Max(maxElem, arr[j]);
maxSum = Math.Max(maxSum, maxElem * (j-i+1) + Helper(arr, n, k, memo, j+1));
}
return memo[i] = maxSum;
}
public int MaxSumAfterPartitioning(int[] arr, int k) {
int n = arr.Length;
int[] memo = new int[n];
Array.Fill(memo, -1);
return Helper(arr, n, k, memo, 0);
}
public static void Main(string[] args) {
var sol = new Solution();
int[] arr = {1, 15, 7, 9, 2, 5, 10};
int k = 3;
Console.WriteLine(sol.MaxSumAfterPartitioning(arr, k));
}
}This Python function adopts a recursive strategy wrapped in memoization to prevent recalculations of already solved segments. It systematically evaluates possible partitions starting from the 0th index and determines maximum sums through recursive calls.
Time Complexity: O(n * k) reduced by the memoization technique.
Space Complexity: O(n) for memoization, effectively moderating complexity.
Approach 3: Dynamic Programming
We define f[i] to represent the maximum element sum of the first i elements of the array after separating them into several subarrays. At the beginning, f[i]=0, and the answer is f[n].
We consider how to calculate f[i], where i geq 1.
For f[i], its last element is arr[i-1]. Since the maximum length of each subarray is k, and we need to find the maximum value in the subarray, we can enumerate the first element arr[j - 1] of the last subarray from right to left, where max(0, i - k) \lt j leq i, and maintain a variable mx during the process to represent the maximum value in the subarray. The state transition equation is:
$
f[i] = max{f[i], f[j - 1] + mx times (i - j + 1)}
The final answer is f[n].
The time complexity is O(n times k), and the space complexity is O(n), where n is the length of the array arr$.
function maxSumAfterPartitioning(arr: number[], k: number): number {
const n: number = arr.length;
const f: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
let mx: number = 0;
for (let j = i; j > Math.max(0, i - k); --j) {
mx = Math.max(mx, arr[j - 1]);
f[i] = Math.max(f[i], f[j - 1] + mx * (i - j + 1));
}
}
return f[n];
}func maxSumAfterPartitioning(arr []int, k int) int {
n := len(arr)
f := make([]int, n+1)
for i := 1; i <= n; i++ {
mx := 0
for j := i; j > max(0, i-k); j-- {
mx = max(mx, arr[j-1])
f[i] = max(f[i], f[j-1]+mx*(i-j+1))
}
}
return f[n]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with One-Dimensional Array | Time Complexity: O(n * k) because of the nested loop structure per index. |
| Recursive Approach with Memoization | Time Complexity: O(n * k) reduced by the memoization technique. |
| Dynamic Programming | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Partition Array for Maximum Sum easy or hard?
Partition Array for Maximum Sum is considered a medium difficulty problem. The main challenge is recognizing the dynamic programming state and efficiently evaluating partition sizes without recomputing segment maximums.
Partition Array for Maximum Sum Python/Java solution
Both Python and Java implementations follow the same DP pattern. Create a dp array of size n+1, iterate from left to right, and for each index evaluate partitions of length up to k while tracking the maximum value in the segment. Update dp[i] with the best computed sum.
How to solve Partition Array for Maximum Sum in O(n*k)?
Use dynamic programming with dp[i] representing the best result for the first i elements. For every i, iterate backward up to k elements, track the maximum value in that window, and update dp[i] using dp[i-len] + maxValue * len. This bounded backward scan keeps the complexity at O(n*k).
What is the best approach for Partition Array for Maximum Sum?
The most effective approach uses one-dimensional dynamic programming. Define dp[i] as the maximum sum achievable for the first i elements. For each index, check partitions of length 1 to k ending at that position and track the maximum value within the segment. This produces an O(n*k) time and O(n) space solution.
Is Partition Array for Maximum Sum asked at Google/Amazon/Meta?
Dynamic programming partition problems similar to this appear in interviews at companies like Amazon, Google, and Meta. The problem tests understanding of DP state design, optimal substructure, and efficient iteration over partition sizes.
What data structure is used in Partition Array for Maximum Sum?
The main structure is a one-dimensional dynamic programming array. The algorithm also uses simple variables to track the maximum element in a sliding window while iterating backward up to k elements.
What is the time complexity of Partition Array for Maximum Sum?
The optimal solution runs in O(n*k) time. For each element in the array, the algorithm checks up to k possible partition sizes while maintaining the segment maximum. Space complexity is O(n) for the dynamic programming array.