华为4.22笔试：第3题最大最小值动态规划解法（附原题）

题目复述：
对于一列有m个正整数元素的数组，用k-1个隔板把该数组分成连续的k份，每一份均非空。找出一种分法，使得这k份中每份求和的最小值达到最大。且若多种情况同时达到最优，那么找出一种使得靠近左侧部分的和更大的情况。最后输出原数组加分隔符'/'的形式。
比如一个数组100 200 300 400 500 600 700 800 900，将其分为3份，那么100 200 300 400 500 / 600 700 / 800 900 这种分法的最小和是600+700=1300，且不存在其他分法使其更大。
再比如1 1 1 1 1 1 1 1，k=3。有6种分法达到最优：
1 1 / 1 1 1 / 1 1 1
1 1 1 / 1 1 / 1 1 1
1 1 1 / 1 1 1 / 1 1
1 1 / 1 1 / 1 1 1 1
1 1 / 1 1 1 1 / 1 1
1 1 1 1 / 1 1 / 1 1
那么让左侧部分尽量大，就输出 1 1 1 1 / 1 1 / 1 1。（即第一部分尽量大，若第一部分相同，则第二部分尽量大，以此类推）

输入：第一行m,k，分别表示数组元素个数与分割的份数；第二行一组正整数，为待分割数组。
输出：一行分割后结果，在分割点用' / '标出，如上面例子输出 1 1 1 1 / 1 1 / 1 1。

思路：

1. 用一个dp数组来存储最小和，具体地，dp[i][j]用来存储将前j+1个元素分为i+1份的最大最小和（注意i,j满足i<=j<=m-k+i)
2. i=0时，dp[i][j]就是前j+1个元素的和，因为此时只分为1份。
3. 考虑i>0，计算dp[i][j]的时候，从第j个元素开始向左遍历，直到找到第一个h，使得h和j之间的数组的和>=dp[i-1][h-1]，停下来。如果可以找到h，且h不等于j，那么分点一定是h或h+1 （注意这里是该算法的核心），因为其它点确定的最大最小和一定不大于这两个点，并且如果等于，那么一定是在这两个点上使得左侧部分和更大。只需比较分点是h和h+1时哪个最大最小和更大就行。如果找不到h，或者h=j，那么就是边界情况，额外讨论即可。
4. 找到最大最小和后再进行分点选取。设置一个分点数组sp。此时从右向左遍历，初始化s=0，每次s加上当前位置的值，若某个位置s更新后刚好满足s>=最大最小和，那么将该位置加入sp且重置s为0，循环此操作直至sp的元素个数为k-1为止。

m, k = tuple(map(int, input().split()))
nums = list(map(int, input().split()))
dp=[[0 for j in range(m)] for i in range(k)]
s=0
for i in range(m):
    s+=nums[i]
    dp[0][i]=s
for i in range(1,k):
    for j in range(i,m-k+i+1):
        t=nums[j]
        h=j
        if t>=dp[i-1][h-1]:
            dp[i][j] = dp[i - 1][h - 1]
        else:
            while t<dp[i-1][h-1] and h>i:
                u=t
                h-=1
                t+=nums[h]
            if t>=dp[i-1][h-1]:
                if u>=dp[i-1][h-1]:
                    dp[i][j]=u
                else:
                    dp[i][j]=dp[i-1][h-1]
            else:
                dp[i][j]=t
val=dp[-1][-1]
s=0
sp=[]
count=0
for i in range(m-1,-1,-1):
    s+=nums[i]
    if s>=val:
        s=0
        sp.append(i)
        count+=1
        if count==k-1:
            break
nums=list(map(str,nums))
n=len(sp)
for i in range(n):
    nums.insert(sp[i],'/')
print(' '.join(nums))