Skip to main content
Talentd

Partition Array for Maximum Sum - Solution & Explanation

MediumArrayDynamic Programming20 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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 <= 500
  • 0 <= arr[i] <= 109
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * k) since for each index, we consider up to k previous elements.
Space Complexity: O(n) for the dp array.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * k), due to exponential recursive divisions curtailed by memoization.
Space Complexity: O(n) for memoization storage.

Try this approach in the editor →

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$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with One-Dimensional Array

Time Complexity: O(n * k) since for each index, we consider up to k previous elements.
Space Complexity: O(n) for the dp array.

Recursive Approach with Memoization

Time Complexity: O(n * k), due to exponential recursive divisions curtailed by memoization.
Space Complexity: O(n) for memoization storage.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(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

Video Solution

DP 54. Partition Array for Maximum Sum | Front Partition 🔥 • take U forward • 154,142 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Partition Array for Maximum Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Substring Partition of Equal Character Frequency

Next

Partition String Into Minimum Beautiful Substrings