算法题求解：分隔数组求最大和 子数组长≤k替换为最大值求最大总和

这个问题用动态规划求解可以把暴力法的指数级时间复杂度降到多项式级别，是这类数组分隔求最值问题的通用解法。

• 状态定义：用dp[i]表示数组前i个元素（对应数组下标0~i-1）按规则分隔后能得到的最大元素和。
• 初始状态：dp[0] = 0，代表0个元素的和为0。
• 状态转移逻辑：对于第i个位置，最后一个连续子数组的长度可以取1到min(k, i)之间的任意值。我们从i-1位置倒推遍历最多k个位置，记遍历到的位置为j（j的范围是max(0, i-k) <= j <= i-1），遍历过程中维护j到i-1区间的最大值current_max，此时如果最后一个块是[j, i-1]，那么总收益为dp[j] + current_max * (i-j)，取所有可能收益的最大值作为dp[i]的取值。

这个基础DP解法的时间复杂度是O(nk)，n是数组长度，常规数据规模下运行效率足够。
如果需要还原出题目要求的拼接后的新数组，只需要额外维护一个prev数组，记录每个i取到最大收益时对应的分割点j，最后从数组末尾倒推就能得到所有块的起止位置，再把每个块填充为块内最大值、按顺序拼接即可。
如果k的取值和n同量级，还可以用单调队列维护滑动窗口的最值与最优转移点，把时间复杂度进一步优化到O(n)，大部分场景下基础DP实现已经够用。

def get_max_partition_result(A, k):
    n = len(A)
    dp = [0] * (n + 1)
    prev = [0] * (n + 1)  # 记录分割点用于还原结果数组
    
    for i in range(1, n + 1):
        current_block_max = 0
        max_total = 0
        best_split = i - 1
        # 往前枚举最后一个块的所有可能长度
        for j in range(i - 1, max(i - k - 1, -1), -1):
            current_block_max = max(current_block_max, A[j])
            current_total = dp[j] + current_block_max * (i - j)
            if current_total > max_total:
                max_total = current_total
                best_split = j
        dp[i] = max_total
        prev[i] = best_split
    
    # 倒推还原结果数组
    new_array = []
    pos = n
    while pos > 0:
        split_pos = prev[pos]
        block_val = max(A[split_pos:pos])
        new_array.extend([block_val] * (pos - split_pos))
        pos = split_pos
    new_array.reverse()
    return dp[n], new_array

# 测试题目样例
A = [1, 15, 7, 9, 2, 5, 10]
k = 3
max_sum, newArray = get_max_partition_result(A, k)
print(max_sum)  # 输出84，对应15*3 +9 +10*3 = 84
print(newArray) # 输出[15, 15, 15, 9, 10, 10, 10]，和示例一致

内容的提问来源于stack exchange，提问作者user1161098