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

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

为了使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))