Split the given array into K segments with Min-max sum-CodePudding

I wrote this code for splitting an array S into k continuous segments, to minimize the largest sum among these k segments. Here S is a sequence so I cannot change the ordering of the elements. Here is the code:

def Opt(i, j):
    n = len(i)
    sum = [0]*(n 1)
    dp = [[0 for a in range(n 1)] for a in range(2)]
    for a in range(0,n):
        sum[a 1] = i[a]   sum[a]
        dp[0][a 1] = float('inf')
        dp[1][a 1] = float('inf')
    for a in range(1,j 1):
        for b in range(1,n 1):
            for c in range(a-1,b):
                dp[a%2][b] = min(dp[a%2][b], max(dp[(a-1)%2][c], sum[b]-sum[c]))
    return dp[j%2][n]

# Driver Code
if __name__ == '__main__':
    S = [7,2,5,10,8]
    k = 2
    M = sum(S)/len(S)
    ans = Opt(S,k)
    print(ans)

This works perfectly well. But I would also like to return the segments for which I have calculated the min-max sum. For example, for the array S = [3,3,7,33] and k=3 this algorithm returns the answer '33' but I want to return the segments as [[3,3],[7],[33]]. But I am not being able to do it. Can anybody help me?

CodePudding user response：

You need to use a traceback technique (not sure if that name is widely used, or just in bioinformatics).

As you fill in your dynamic programming matrix with the best possible score for each sub-problem, you also fill in a traceback matrix that encodes the solution for each sub-problem.

For your problem, the traceback could store the optimal break-points for the sub-arrays:

def Opt(i, j):
    n = len(i)
    sum = [0]*(n 1)
    dp = [[0 for a in range(n 1)] for a in range(2)]
    tb = [[[] for a in range(n 1)] for a in range(2)]

    for a in range(0,n):
        sum[a 1] = i[a]   sum[a]
        dp[0][a 1] = float('inf')
        dp[1][a 1] = float('inf')

    for a in range(1,j 1):
        for b in range(a   1,n 1):
            for c in range(a - 1, b):
                # if c should be a breakpoint, then...
                if max(dp[(a-1)%2][c], sum[b]-sum[c]) < dp[a%2][b]:
                    # ...update the best score, and...
                    dp[a%2][b] = max(dp[(a-1)%2][c], sum[b]-sum[c])
                    # ...update the solution
                    tb[a%2][b] = tb[(a - 1)%2][c]   [c]

    # extract optimal sub-arrays
    starts = tb[j%2][n]
    ends = starts[1:]   [n]
    sub_arrays = [i[s:e] for s, e in zip(starts, ends)]

    return sub_arrays


S = [7,2,5,10,8]

Opt(S, 2)              # ==> [[7, 2, 5], [10, 8]]
Opt(S, 3)              # ==> [[7, 2, 5], [10], [8]]
Opt([3, 7, 7, 33], 3)  # ==> [[3, 7], [7], [33]]