Divide Array into K Contiguos Partitions Such That Sum of Maximum Partition Is Minimum

Partition an array into K subarrays with minimal difference

Ok, I think I did it!

The idea is following: we assume that minimum sum interval always starts from 0. Then we start to enumerate maximum sum intervals, starting from the right boundary of the minimal interval. We build DP problem for current max interval to determine a minimum maximal sum. After that you update result and rotate an array by one.

My code is not perfect in a way that I compute current sums each iteration. One can pre-compute them and just index them each time.

This code might have some bugs, but it passes all test that I have.

#include <climits>
#include <cstdio>
#include <cstring>

const int max_value = 200000;
const int max_n = 50;
const int max_k = 20;

int deps[max_n];

int max (int x, int y) {
  return x > y ? x : y;
}

int min (int x, int y) {
  return x < y ? x : y;
}

int sum (int a[], int start, int end) {
  int res = 0;

  for (int i = start; i <= end; ++i) res += a[i];

  return res;
}

int k_partitioning(int k, int n, int deps[]) {
  int res = max_value;
  for(int offset = 0; offset < n; ++offset) {
    int l_min = 0;
    for(int r_min = l_min; r_min < n; ++r_min) {
      int min_sum = sum (deps, l_min, r_min);

      int dp[k][n];
      for (int s = 0; s < k; ++s) {
        for (int q = 0; q < n; ++q) {
          dp[s][q] = max_value;
        }
      }
      // assuming that current sum is a target sum
      dp[0][r_min-l_min] = min_sum;

      for(int p = 1; p < k; ++p) {
        for(int l_max = r_min; l_max < n; ++l_max) {
          for(int r_max = l_max; r_max < n; ++r_max) {
            int max_sum = sum(deps, l_max+1, r_max);

            if (max_sum >= min_sum) {
              dp[p][r_max] = min(dp[p][r_max], max(dp[p-1][l_max], max_sum));
            }

          } // l_maxs
        } // r_maxs
      } // partitions

      // skip incorrect partitioning, when not all K partitions were used
      if (dp[k-1][n-1] == max_value) continue;

      // update difference
      res = min (res, dp[k-1][n-1] - min_sum);
    } // end min sum seg
    int tmp[n];
    for (int i = 0; i < n; ++i) {
      int new_idx = i + n - 1;

      tmp[new_idx % n] = deps[i];
    }

    for(int i = 0; i < n; ++i) deps[i] = tmp[i];

  } // start min sum seg
  return res;
}

int main(int argc, char* argv[]) {
  int k = 0;
  scanf("%d", &k);

  int n = 0;
  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {
    scanf("%d", &deps[i]);
  }

  printf ("%d\n", k_partitioning(k, n, deps));

  return 0;
}

How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?

Use binary search.

Let max sum range from 0 to sum(array). So, mid = (range / 2). See if mid can be achieved by partitioning into k sets in O(n) time. If yes, go for lower range and if not, go for a higher range.

This will give you the result in O(n log n).

PS: if you have any problem with writing the code, I can help but I'd suggest you try it first yourself.

EDIT:

as requested, I'll explain how to find if mid can be achieved by partitioning into k sets in O(n) time.

Iterate through the elements till sum is less than or equal to mid. As soon as it gets greater than mid, let it be part of next set. If you get k or less sets, mid is achievable, else not.

Divide an array into k partitions subarray that have minimum difference

The optimal solution to the problem you've stated is NP-hard, but here's a simple naive approach that does fairly well for many cases:

def naive_partition(a, k):
    result = [[] for _ in range(k)]
    sums = [0] * k
    for x in sorted(a, reverse=True):
        i = sums.index(min(sums))
        sums[i] += x
        result[i].append(x)

    return result


print(naive_partition([1, 2, 3, 4, 7], 3))

Result:

[[7], [4, 1], [3, 2]]

Maximize the minimum subarray sum out of all subarrays when an array is divided into K subarrays/groups

First off, let's start with an example that would test your intuition as to whether there is a single solution for a given A and K.

For A=[1,2,3,4,5] and K=2, we could have the partitions P and minimum subarray sum v as follows:

P = [1], [2,3,4,5]  ; v = 1
P = [1, 2], [3,4,5] ; v = 3
P = [1,2,3], [4,5]  ; v = 6
P = [1,2,3,4], [5]  ; v = 5

As you can see, there are multiple ways to partition A into K subarrays, and each may have a different minimum subarray sum value.

That said, we can now analyze what is going on in this solution. This algorithm presents a common approach. Basically, you have a space of acceptable answers, and you search through that space for a best answer using binary search.

In this particular problem, the least possible answer is actually the smallest value in the array, but 0 can be used without any issues. The maximum possible answer would be the sum of all the values in the array. (i.e., if K==1) So you go through those possible answers and see if you can partition the array into K subarrays, with the smallest subarray sum being mid, which is the current potential answer you are checking. The space of possible answers is suitable for this binary search strategy, because up to a certain value v, the number of subarrays with sums that are greater than or equal to mid is less than K. And starting with the value v, you can actually have >= K subarrays with sums greater than or equal to mid.

At each step (i.e., iteration of binary search) you try and form groups so that sum of each group is >= mid. As soon as a group's sum exceed that threshold, you start a new group. So, in a sense, you are correct, because for a particular value of mid, there is only one optimal way to partition the array: make sure each subarray has a sum >= K and as soon as this requirement is satisfied, start partitioning a new subarray from the original array. This is a locally optimal strategy that ensures globally optimal result. (i.e., greedy) But what actually ensures maximizing the minimum subarray sum is the binary search. By iterating over the space of possible answers, and picking the least acceptable value once it is done, binary search ensures that, among the answers that satisfy the given constraints, the smallest one (i.e., v) is picked.

If you are still having a hard time digesting the strategy of this algorithm, try to consider it from a different perspective. It isn't the partitioning you're looking for, but the least value v for which you can create K continuous groups, sum of each would be greater than or equal to v. To ensure you have as many acceptable subarrays for a given mid, you keep adding new elements to a subarray as long as the requirements (i.e., sum >= mid) are not met, and start forming a new subarray as soon as a subarray reaches that threshold. So, for each mid, numOfSubArrays returns you the maximum number of acceptable groups you can form. And overall, binary search just finds out the value v, the least value for which numOfSubArrays returns something greater than or equal to K.

Split array into four boxes such that sum of XOR's of the boxes is maximum

There are several things to speed up your algorithm:

Build in some start-up logic: it doesn't make sense to put anything into box 3 until boxes 1 & 2 are differentiated. In fact, you should generally have an order of precedence to keep you from repeating configurations in a different order.
Memoize your logic; this avoids repeating computations.
For large cases, take advantage of what value algebra exists.

This last item may turn out to be the biggest saving. For instance, if your longest numbers include several 5-bit and 4-bit numbers, it makes no sense to consider shorter numbers until you've placed those decently in the boxes, gaining maximum advantage for the leading bits. With only four boxes, you cannot have a num from 3-bit numbers that dominates a single misplaced 5-bit number.

Your goal is to place an odd number of 5-bit numbers into 3 or all 4 boxes; against this, check only whether this "pessimizes" bit 4 of the remaining numbers. For instance, given six 5-digit numbers (range 16-31) and a handful of small ones (0-7), your first consideration is to handle only combinations that partition the 5-digit numbers by (3, 1, 1, 1), as this leaves that valuable 5-bit turned on in each set.

With a more even mixture of values in your input, you'll also need to consider how to distribute the 4-bits for a similar "keep it odd" heuristic. Note that, as you work from largest to smallest, you need worry only about keeping it odd, and watching the following bit.

These techniques should let you prune your recursion enough to finish in time.

faster algorithms for minimum maximum contiguous k partition

Ok so apparently this was closed for being "off-topic"!?
But it's back up now so anyway, I found the solution to be binary searching the answer. Sorry I forgot one of the constraints was that the sum of all the integers would not exceed 2^64. So let C = cumulative sum of all integers. Then we can binary search for the answer using a

bool isPossible(int x)

function which returns true if it is possible to divide S into k partitions with maximum partition sum less than X. isPossible(int x) can be done in O(n) (by adding everything from left to right and if it exceeds x make a new partition). So the total running time is O(n*log(s)).

Divide an array into k or less subparts to minimize the maximum sum of each part

You could use a greedy solution if you want a good-enough solution:

def minmax(lst, k):
    lst = sorted(lst, reverse=True)  # biggest numbers first is usually better
    subs = [[] for _ in xrange(k)]   # create the lists for the subarrays

    while lst:
        subs[0].append(lst.pop(0))         # append to the one with lowest sum
        subs.sort(key=sum)                 # sort by sum (lowest first)
        print subs                   # print the subarrays while creating them

    return sum(subs[-1])    # we have sorted by sums, last has the biggest sum

This does not guarantee to produce the best result, but it works pretty well.

k = 2

This is your example:

print 'result is %d' % minmax([5, 10, 21, 20], 2)

Output

[[], [21]]
[[20], [21]]
[[21], [20, 10]]
[[21, 5], [20, 10]]
result is 30

Well, it found a better solution than the one you showed.

k >= 4

Let's try with k=4 and k=5

>>> print 'result is %d' % minmax([5, 10, 21, 20], 4)
[[], [], [], [21]]
[[], [], [20], [21]]
[[], [10], [20], [21]]
[[5], [10], [20], [21]]
result is 21

>>> print 'result is %d' % minmax([5, 10, 21, 20], 5)
[[], [], [], [], [21]]
[[], [], [], [20], [21]]
[[], [], [10], [20], [21]]
[[], [5], [10], [20], [21]]
result is 21

You could also add this code to the beginning of the function to directly return the max of lst when k >= len(lst):

def minmax(lst, k):
    if k >= len(lst):
        return max(lst)
    ....

Minimum Makespan Problem

This type of problem is famous with the name of Minimum Makespan Problem, searching for it you will retrieve lots of information about algorithms that are guaranteed to produce the optimal result, but their explanation is far too complex for a stack overflow answer, while the greedy one is fun and instructive.

Algorithm help: how to divide array into N segments with least possible largest segment (balanced segmenting)

I like ILoveCoding's approach. Here's another way that takes O(MN^2) time, which will be faster if N and M are small but the numbers in the array are very large (specifically, if log(sum) >> MN, which is possible but admittedly doesn't sound very realistic). It uses dynamic programming.

Let's consider partitioning just the subarray consisting of the first i <= N entries into j <= M segments. Let f(i, j) be the weight of the largest segment in the best solution for this subproblem -- i.e. the weight of the largest segment in that j-partition of the first i numbers whose largest segment is smallest among all such partitions. We want to compute f(N, M), as well as a (there may be more than one) partition that corresponds to it.

It's easy to compute f(i, 1) -- that's just the sum of the first i elements:

f(i, 1) = x[1] + ... + x[i]

To compute f(i, j) for j >= 2, observe that element i must be the final element of some segment that starts at some position 1 <= k <= i, and which is preceded by j-1 segments -- and in any optimal solution for parameters (i, j), those j-1 preceding segments must themselves be optimal for parameters (k-1, j-1). So if we consider every possible start position k for this final segment and take the best, we will calculate the best j-partition of the first i elements:

[EDIT 3/2/2015: We need to take the max of the new segment and the largest remaining segment, instead of adding them!]

f(i, j >= 2) = minimum of (max(f(k-1, j-1), x[k] + ... + x[i])) over all 1 <= k <= i

If we try k values in decreasing order, then we can easily build up the sum in constant time per k value, so calculating a single f(i, j) value takes O(N) time. We have MN of these values to compute, so the total time needed is O(MN^2).

One more boundary condition is needed to forbid trying to partition into more segments than there are elements:

f(i, j > i) = infinity

Once we have calculated f(N, M), we could extract a corresponding partition by tracing back through the DP matrix in the usual way -- but in this case, it's probably easier just to build the partition using ILoveCoding's greedy algorithm. Either way takes O(N) time.