Algorithm splitting array into sub arrays where the maximum sum among all sub arrays is as low as possible

Question

Let's say we have an array of ints: a = {2,4,3,5}

And we have k = 3.

We can split array a in k (3) sub arrays in which the order of the array cannot be changed. The sum of each sub array has to be as low as possible so that the maximum sum among all sub arrays is as low as possible.

For the above solution this would give {2, 4}, {3}, {5} which has a maximum sum of 6 (4 + 2).

A wrong answer would be {2}, {4, 3}, {5}, because the maximum sum is 7 (4 + 3) in this case.

I've tried creating a greedy algorithm which calculates the average of the entire array by summing all ints and dividing it by the resulting amount of sub arrays. So in the example above this would mean 14 / 3 = 4 (integer division). It will then add up numbers to a counter as long as it's < than the average number. It will then recalculate for the rest of the sub array.

My solution gives a good approximation and can be used as heuristic, but will not always give me the right answer.

Can someone help me out with an algorithm which gives me the optimal solution for all cases and is better than O(N²)? I'm looking for an algorithm which is O(n log n) approximately.

Thanks in advance!

Gaines

Are you sure there is a O(n log n) solution, or you hope for a O(n log n) solution? Just asking for a direction to think. Also is there any constrains for sub-array or the int? (Why the answer is not {2},{3},{4},{5} which gives 5 as answer? Does the int non-negative? etc) – Krupp

Yes I'm positive there is one. I am thinking about a greedy algorithm or a divide and conquer algorithm. There are some constaints indeed: - The order cannot be changed. - The amount of splits is given and cannot be more or less than that (it's 3 in my example). - The ints are all positive (don't know if this would matter for the solution). – Gaines

Answer 1

We can use binary search to solve this problem.

So, assume that the maximum value for all sub-array is x, so, we can greedily choose each sub-array in O(n) so that the sum of each subarray is maximum and less than or equals to x. After creating all subarray, if the number of sub-array is less than or equal to k, so x is one possible solution, or else, we increase x.

Pseudocode:

int start = Max_Value_In_Array;
int end = Max_Number;

while(start <= end)
   int mid = (start + end)/2;
   int subSum = 0;
   int numberOfSubArray = 1;
   for(int i = 0; i < n; i++){
      if(subSum + data[i] > mid){
          subSum = data[i];
          numberOfSubArray++;
      }else{
          subSum += data[i];
      }
   }
   if(numberOfSubArray <= k)
       end = mid - 1;
   else
       start = mid + 1;

Time complexity O(n log k) with k is the maximum sum possible.

Above

How would this give me the resulting sub arrays? – Gaines

@Gaines after found the minimum value x, you just need to reconstruct using the same way as when you count number of sub array – Above

@PhamTrung Ah I see, thank you. I've tried implementing the algorithm in C# link, but I this got caught in an endless loop. Anything I'm missing? – Gaines

@Gaines your program may cause number overflow. Because for end, you assign int.MaxValue. – Above

@PhamTrung Because in your pseudo code, you say end = Max_Number. What is this Max_Number then? – Gaines

@Gaines do you understand binary search? if your program can cause number overflow, what should be a general solution? I think all these questions you should figure out yourself, there is no special trick about them. – Above

@PhamTrung I'm sorry if I misformulated my question, but binary search needs the array to be sorted. In this case, the array cannot be changed in order. The array is as it is. Therefore I'm afraid Binary Search will not work. – Gaines

@Gaines haizz, if you think binary search can only be used that way, you need to study more. And read my answer few more times to really understand how it works. To be honest, this problem is a little bit too hard for you. Try easier one and come back when you are ready. – Above

@PhamTrung That's for as far as I know binary search works. I do not have a lot of experience with it, but am eager to learn. This problem might be too hard for me, but I still want to understand. Being able to understand this problem could be an eye opener to others. I thank you for your help so far. I've been trying to figure out how I should interpret those first 'start' and 'end' values, but didn't manage to understand what those start values should be. – Gaines

@Gaines It is normal to for one to learn by months or years in order to solve a problem (actually, all of us done that) . If you don't want to put in enough time and effort, you will never learn. The problem is, even though you have read the answer, you still cannot understand it properly, which is an indicator that, your skill are not there yet, and it is pointless to sitting around and just try to solve one single problem. What you should do is improve your skill and knowledge, only then, come back and try one more time. – Above

@Gaines So, for this question, the binary search is not to looking for any element in the array, but to look for the minimum number x, which we can split array into k segment, whose sum less than or equals to x. And why binary search can be used in this case? because of a property that, with a value x, if we can divide the array into k segment, so, with value greater than x, we can also divide the array into k segments. So, the requirement for binary search is satisfied. – Above

@Robinhopok, so imagine that we have an invisible array, which contains value from max value in array to sum of array, we are doing a search on that array, not on the original array. – Above

@PhamTrung I know I won't be fully knowledged when I would understand this problem if you just gave the answer. It will take time and it will take a lot of practise. I know that. I did not come here to seek that sort of advice, tho I appreciate it. My only question is: Max_Value_In_Array and Max_Value are both ambigious. What is the Max_Value_In_Array? Is this the max value of an element in the array or is it the index? Then if that's the case, what does Max_Value mean? Is it the same? It's not clear what those values represent. All I ask is some clearification about that :) – Gaines

@Gaines so, the question is, how to find the start and end value for a binary search. The answer is very simple, start value, in this case, is the minimum possible value which x can achieved. As the data array only contains positive number, it is meaningless to choose a value which is smaller than the largest element in the array, or Max_Value_In_Array. Similarly, what should be the end value for binary search? It should be the largest value possible for x, and again, as this array only contains positive values, it is the sum of the whole array. – Above

@Gaines And for your overflow problem, just change from int to long will solve the problem. – Above

@PhamTrung Thank you for the explanation. I understand now. The mid variable, shouldn't that be ( start + end ) / 2? – Gaines

@Gaines Yup, just fixed it, thanks. Glad you understand it. If this answers your question, don't forget to mark it as accepted. – Above

Let us continue this discussion in chat. – Gaines

Does your algorithm give the optimal solution? Suppose for an x, the greedy algorithm fails to find the splitting resulting in k subarrays, then your algorithm will skip considering x as the answer, which might result in a suboptimal result. For example, the array might be [1,2, 4, 5], and x = 6, k = 2. The greedy algorithm will split this into [1,2], [4], [5], then the number of subarrays will be greater than k. However we can split this into [1,5], [2, 4], and the number of subarrays is exactly k. – Austin

@ZhongweiZhao The question says that the "order of the array cannot be changed". Your array was [1, 2, 4, 5], but your splitting was [1, 5], [2, 4], which isn't the same order. – Valtin