划分阵列，使子阵列最大值之和最小化

Question

我只能想出一个蛮力的办法来解决这个问题。有兴趣看看AlgoSo社区会想出什么

给出一个arra和一个整数x（1<；x<；=len（a））。在不重新排序的情况下，将阵列划分为x个子阵列s1, s2....sx ，以使max(s1) + max(s2)....+ max(sx)的总和是子阵列总和的所有可能组合中的最小值（参见下面的示例）。返回一个包含x-1索引的数组，其中包含发生拆分的索引i（不包括）

例如：

a = [10,30,40,20,50]
x = 2
return = [1]

将索引1处的数组拆分为[10]和[30,40,20,50]

将产生max([10]) + max([30,40,20,50]) = 60，这是所有其他拆分数组方法中的最小值

其他可能的拆分-

• 无法在索引0处拆分，因为这样只会导致1个数组和x=2
• 在指数2处拆分=最大值（[10,30]）+最大值（[40,20,50]）=80
• 如果在指数3处拆分，则结果为90
• 如果在指数4处拆分，则结果为90
• 不允许在索引5处拆分，因为这样只会导致1个数组和x=2

Answer 1

如果你能将暴力组织成记忆化，那么暴力也没那么糟糕

该方法可以递归地进行左右分割，以确定最佳解决方案，将每个左侧前缀与最佳解决方案相结合，从而减少右侧分割的次数。由于这将多次计算同一个右侧拆分，因此内存化（将过去的结果保留在内存中以供重用）将使大多数探索分支短路

from functools import lru_cache
from itertools import accumulate
def minMaxSum(A,x):
    
    @lru_cache()                # memoization for
    def findBest(start,splits): # best split from start position to end of A

        R = A[start:] # right-side/remaining elements

        # base cases (no recursion)
        if splits == 1:      return max(R),[R]
        if splits == len(R): return sum(R),[[r] for r in R]
        
        # progressively increasing size of left side subarray
        bestSum   = sum(R)+1           
        maxLeft   = 0
        for i,r in enumerate(R[:len(R)-splits+1],1):
            if r >= bestSum: break   # won't improve on best at this point
            maxLeft = max(maxLeft,r) # max for left side          
            subSum,subArrays = findBest(start+i,splits-1) # recurse right side
            subSum += maxLeft
            if subSum>=bestSum: continue # track improvement to best solution
            bestSum   = subSum
            bestSplit = [R[:i],*subArrays] # left side + best right side solution
        return bestSum,bestSplit
    
    # convert to break indexes and return solution
    maxSum,subArrays = findBest(0,x)
    breaks = list(accumulate(map(len,subArrays)))[:-1]
    return breaks,maxSum,subArrays
            

输出：

print(*minMaxSum([10,30,40,20,50],2))
# [1] 60 [[10], [30, 40, 20, 50]]
    
print(*minMaxSum([10,30,40,20,50],3))
# [1, 2] 90 [[10], [30], [40, 20, 50]] 

print(*minMaxSum([40,30,40,20,50],3))
# [3, 4] 110 [[40, 30, 40], [20], [50]]

print(*minMaxSum([40,25,30,45,40,20,35,50],5))
# [1, 2, 5, 6] 180 [[40], [25], [30, 45, 40], [20], [35, 50]]

A = [i%5+1 for i in range(37)]
x = 11
print(*minMaxSum(A,x))
# [1, 2, 5, 6, 7, 10, 11, 12, 35, 36] 27
# [[1], [2], [3, 4, 5], [1], [2], [3, 4, 5], [1], [2],
# [3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5], [1], [2]]

Answer 2

这是一个动态规划问题

首先建立以下数据结构

for each position in the array
    for each count of how many splits
        (current max, sum of maxes, position of last split)

例如，在您的问题中，数据结构如下所示：

[   # One group, no splits
    [(10, 10, 0)], # 2 groups, 1 split
    [(30, 30, 0), (30, 40, 1)],
    [(40, 40, 0), (40, 50, 1), (40, 80, 2)],
    [(40, 40, 0), (20, 50, 1), (20, 70, 3)],
    [(50, 50, 0), (50, 60, 1), (50, 100, 2)], # the choices are equal
]

这可以通过简单的双循环创建。你从[[(a[0], a[0], 0)]]开始。要计算i, j项，您必须查看在(i-1, j-1)项之后启动一个新组，或者将当前元素添加到(i-1, j)项中的最后一个组

完成此操作后，从阵列的最后一个位置和所需的分割数开始。数据结构告诉您上一次拆分的位置，然后您转到该位置并向下拆分一次，以找到前一次拆分的位置。沿着饼干屑的痕迹往回走，你会发现所有的裂口

在您的示例中，(len(a), x)条目位于(4, 1)，并且具有值(50, 60, 1)。上一个条目位于(1, 0)，其值为(10, 10, 0)。我们忽略边界处的分裂，得到[1]作为答案

如果你想做x=3，那么你应该从(50, 100, 2)开始，回到(40, 50, 1)，然后到(10, 10, 0)，得到[1, 2]的答案

Answer 3

为了使Max（sx）尽可能小，我们应该始终努力创建具有尽可能小的数字的子阵列。因此，只需将输入列表划分为具有最小可能值的单个元素列表：

arr = [10,30,40,20,50]
n = 2
a = []

def subarray(a):
    r = []
    while (len(r) <= n-2):
        r.append(a[:1])
        a = a[1:]
    r.append(a)
    return r

def calculate(a):
    r = 0
    for i in subarray(a):
        r += i[-1]
    return r

print(calculate(arr))