MediumArrayDynamic ProgrammingUpdated Sep 2026

1043. Partition Array for Maximum Sum

Asked at TikTok

Difficulty

Medium

Time

O(n * k)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an integer array arr and an integer k. You must cut arr into contiguous pieces (subarrays), where each piece has length between 1 and k. Every element in a piece is replaced by the maximum value inside that piece. After all replacements, you add up the whole array.

Return the largest possible total you can get by choosing the best way to cut the array. Different cuts give different totals, so you must search for the best one.

A piece must be a block of neighbouring elements — you cannot skip elements or reorder them. Every element belongs to exactly one piece.

Cut into pieces, then copy each piece's max

arrmax 15max 9max 101157925100123456Three pieces, each of length at most k = 3.after1515159101010Each element is replaced by its piece's maximum: 45 + 9 +30 = 84.
The cut [1,15,7] [9] [2,5,10] gives 15,15,15 | 9 | 10,10,10 for a total of 84.

Constraints

  • ●1 <= arr.length <= 500
  • ●0 <= arr[i] <= 10^9
  • ●1 <= k <= arr.length
  • ●The answer fits in a 32-bit integer.

Examples

Example 1
Inputarr = [1,15,7,9,2,5,10], k = 3
Output84
WhyCut into [1,15,7], [9], [2,5,10]. The first piece's max is 15, so it becomes 15,15,15. The middle piece stays 9. The last piece's max is 10, so it becomes 10,10,10. Total = 45 + 9 + 30 = 84.
Example 2
Inputarr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output83
WhyThe best cut spreads the large values 7 and 9 across pieces of length up to 4, so those big numbers get copied many times. The resulting total is 83.
Example 3
Inputarr = [1], k = 1
Output1
WhyThere is only one element and the only allowed piece length is 1, so the array stays [1] and the total is 1.

Asked At

1 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →

How to Think About It

1

Greedy choices (always take pieces of length k, or always extend around big numbers) fail on small counterexamples. You need to try the options.

2

Key insight: let dp[i] be the best total for the prefix of length i. The last piece ends at index i - 1 and has some length len from 1 to k.

3

For each len, the piece contributes max(arr[i-len..i-1]) * len, so dp[i] = max over len of dp[i - len] + maxInPiece * len.

4

Compute the running maximum while extending len backward, so each state costs O(k).

5

Walkthrough for [1,15,7,9,2,5,10], k = 3: the best split is [1,15,7] [9] [2,5,10] -> 15*3 + 9 + 10*3 = 84.

Optimal Approach

Step 1: dp = [0] * (n + 1).
Step 2: For i from 1 to n:
cur = 0
For len from 1 to min(k, i):
cur = max(cur, arr[i - len])
dp[i] = max(dp[i], dp[i - len] + cur * len)
Step 3: Return dp[n].

Time: O(n * k). Space: O(n).

DP over prefixes

arrlen = 31157925100123456i-1At i = 7, try the last piece ending at index 6 with length1, 2 or 3.dp01234567dp01304554647484dp[3] = 45 from piece [1,15,7]; dp[7] = 84 is the finalanswer.dp[i] = max over len of dp[i-len] + maxInPiece * lencur = max(cur, arr[i-len]) while len grows
dp[i] is the best total for the first i elements; we try every possible length for the last piece.
ComplexityTime O(n * k)Space O(n)There are n states, and each state tries up to k possible lengths for its last piece; the dp array of size n+1 holds the results.

What Trips People Up in Real Interviews

1

Recomputing the piece maximum from scratch for each length — that adds another factor of k.

2

Off-by-one with 1-indexed dp versus 0-indexed arr. The last piece for dp[i] covers arr[i-len .. i-1].

3

Trying a greedy split. Always ask yourself for a counterexample before committing to greedy on partition problems.

4

Forgetting to cap len at i for the first few positions.

Solution Code

O(n * k) time
def maxSumAfterPartitioning(arr, k):
    n = len(arr)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        cur = 0
        for length in range(1, min(k, i) + 1):
            cur = max(cur, arr[i - length])
            dp[i] = max(dp[i], dp[i - length] + cur * length)
    return dp[n]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Partition Array for Maximum Sum problem?

Partition Array for Maximum Sum asks you to split an array into contiguous pieces of length at most `k`, replace every element of each piece with that piece's maximum, and return the largest possible total. It is a 1D DP where each state tries every possible length for the last piece.

How do you solve Partition Array for Maximum Sum?

The optimal approach runs in O(n * k) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Partition Array for Maximum Sum?

Partition Array for Maximum Sum is asked at TikTok. It is a medium difficulty problem.

What are common mistakes on Partition Array for Maximum Sum?
  • Recomputing the piece maximum from scratch for each length — that adds another factor of `k`.
  • Off-by-one with 1-indexed `dp` versus 0-indexed `arr`. The last piece for `dp[i]` covers `arr[i-len .. i-1]`.
  • Trying a greedy split. Always ask yourself for a counterexample before committing to greedy on partition problems.
  • Forgetting to cap `len` at `i` for the first few positions.