What is the main pattern used in Partition Array for Maximum Sum?

State transition dynamic programming is the core pattern, where dp[i] stores the maximum sum for the first i elements considering subarrays up to length k.

Can k equal the array length in this problem?

Yes, k can range from 1 to the length of arr, allowing the entire array to form one subarray if k equals arr.length.

How do I compute the maximum value for each subarray efficiently?

Within the DP iteration, track the maximum value dynamically while expanding the subarray length up to k to avoid recomputation.

What are the constraints on arr and k?

The array length is 1 to 500, elements range from 0 to 10^9, and k is between 1 and arr.length.

Why is DP necessary instead of a greedy approach?

Greedy fails because local maximums may not yield the global maximum sum; DP correctly considers all partitions ending at each index.

#1043

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

分隔数组以得到最大和

给你一个整数数组 arr ，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。示例 1：输入： arr = [1,15,7,9,…

数组动态规划

题目描述

给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

示例 2：

输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83

示例 3：

输入：arr = [1], k = 1
输出：1

提示：

1 <= arr.length <= 500
0 <= arr[i] <= 10⁹
1 <= k <= arr.length

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示将数组的前 $i$ 个元素分隔成若干个子数组，最终的最大元素和。初始时 $f[i]=0$ ，答案为 $f[n]$ 。

我们考虑如何计算 $f[i]$ ，其中 $i \geq 1$ 。

对于 $f[i]$ ，它的最后一个元素是 $arr[i-1]$ 。由于每个子数组的长度最多为 $k$ ，并且我们需要求得子数组中的最大值，因此，我们可以从右往左枚举最后一个子数组的第一个元素 $arr[j - 1]$ ，其中 $\max(0, i - k) \lt j \leq i$ ，过程中维护一个变量 $mx$ ，表示最后一个子数组中的最大值，那么状态转移方程为：

f[i] = \max\{f[i], f[j - 1] + mx \times (i - j + 1)\}

最终的答案即为 $f[n]$ 。

时间复杂度 $O(n \times k)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $arr$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        f = [0] * (n + 1)
        for i in range(1, n + 1):
            mx = 0
            for j in range(i, max(0, i - k), -1):
                mx = max(mx, arr[j - 1])
                f[i] = max(f[i], f[j - 1] + mx * (i - j + 1))
        return f[n]

speed

复杂度分析

指标	值
时间	complexity is O(N*K) because each element considers up to k previous subarray lengths. Space complexity is O(N) to store dp values for all positions. This handles array sizes up to 500 efficiently without unnecessary recomputation.
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Focus on defining dp[i] correctly and explaining why previous dp values are reused.
question_mark
Expect reasoning about how subarray length limits (k) influence state transitions.
question_mark
Look for explanation of why maximum value in each partition maximizes the sum.

warning

常见陷阱

外企场景

error
Confusing subarray length with number of partitions leads to incorrect dp indices.
error
Failing to update maximum within each subarray for the current length.
error
Using nested loops incorrectly, causing O(N^2) when k is large, instead of O(N*K).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the problem to minimize sum by using subarray minimums instead of maximums.
arrow_right_alt
Allow non-contiguous partitions, requiring different DP or greedy strategies.
arrow_right_alt
Add a constraint on the number of partitions, combining partition count with sum maximization.

help

常见问题

外企场景

继续练习

#1039 多边形三角剖分的最低得分 #1048 最长字符串链 #1049 最后一块石头的重量 II