Splitting an array in K parts
let the array
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2
I need to split the array by K so that the large amount is low.
For example, k = 3
[2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
[2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
[2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
[2, 1], [5, 1], [2, 2, 2] with a large sum of 6.
So the algorithm should return 6.
Which algorithm should I use is a modified version of the KMP algorithm.
Please give me an approach
source to share
I believe dynamic programming can be used for this. Think of it this way: if you make a cut and put the first m elements in the first piece, then the final maximum value will be the minimum value of the sum of the first m elements and the minimum value that you can get by cutting off the last n - m elements into k - 1 pieces. In the basic case, if you run out of elements, the minimum value is & infin ;.
More formally, let S [n, k] be the minimum maximum value you can make using the first n elements of the array if you need to make k cuts. You can record this repetition:
S [0, k] = & infin; for any k (if you have no elements in the array and have to make any number of cuts, the value is infinite).
S [n, k] = min m & le; n {max (A [n] + A [n - 1] + ... + A [n - m], S [n - m, k - 1]} for n> 0 (you remove a certain number of elements from the back, calculating min as the best choice you can make.
You will need to populate the? Table of elements? (nk), and filling the element at position (n ', k') will take time & Theta; (n '). Thus, the total execution time will be & Theta; (n 2 k).
As a heuristic, you can speed this up a bit. In particular, as soon as A [n] + A [n - 1] + ... + A [m] becomes larger than S [n - m, k - 1], you know that you have cleared too many elements into the group in front and hence may stop evaluating large m values. This is just a heuristic, but in practice it can give you some performance benefits.
Hope this helps!
source to share
There's a O(kn)
-time optimization to templatetypedef DP that works like this. Let be the P(i, j)
maximum optimal position of the last boundary between subarrays when dividing the first elements j
into parts i
. Then P(i, j)
does not decrease in i
. We use this fact as follows (lightly tested by Python).
def minmaxsum(A, k):
S = [0] # partial sums
for x in A:
S.append(S[-1] + x)
n = len(A)
# V0 is the optimal objective values for the (i, j) subproblems
V0 = [1e309] * (n + 1) # 1e309 is infinity
V0[0] = 0
for j in range(k):
# V1 is the optimal objective values for the (i + 1, j) subproblems
V1 = []
i0 = 0
for i1 in range(n + 1):
# the while loop is amortized constant-time
while i0 < n and \
max(V0[i0], S[i1] - S[i0]) >= \
max(V0[i0 + 1], S[i1] - S[i0 + 1]):
i0 += 1
V1.append(max(V0[i0], S[i1] - S[i0]))
V0 = V1
return V0[n]
To further improve this solution, probably close to linear time at sufficiently "disconnected" inputs, note that this sum(A) / k
is the lower bound on the cost of any solution. Thus, for the partition by, i
we have a lower bound max(sum(A[:i]) / (k - 1), sum(A[i:]))
. Using this binding, we can use a binary search to find the most likely split points and then evaluate only a few DP records using a constraint to exclude the rest.
source to share