Split into k sub-arrays#9020

Split into k sub-arrays (Editorial)

We'll search for the optimal value using binary search. Obviously, this value cannot be less than $1$ (since the elements of the array are positive integers) and cannot exceed the sum of all elements in the array. Set the boundaries: $l e f t = 1, r i g h t$ left = 1, right = sum of all array elements. The answer is guaranteed to lie within the range $[l e f t; r i g h t]$ [left; right].

Now consider a helper subproblem: is it possible to split the array into $k$ subarrays such that the maximum sum among all $k$ subarrays does not exceed a given value $s_{0}$ s_0? If the array contains at least one element greater than $s_{0}$ s_0, such a split is impossible. Otherwise, we sequentially form subarrays so that the sum of each does not exceed $s_{0}$ s_0. If the total number of resulting subarrays is no more than $k$ , then such a split is considered possible.

Example

In the second example, let us consider possible ways to split the array into subarrays for different values of $s_{0}$ s_0:

Algorithm implementation

Define a constant $M A X = 1 0^{6}$ MAX = 10^6 and an array $m$ .

#define MAX 1000000
int m[MAX];

The function f returns $1$ if the array can be split into $k$ subarrays such that the maximum sum among all $k$ subarrays does not exceed the given value $s_{0}$ s_0.

int f(long long s0)
{
  long long sum = 0;
  int cnt = 1;
  for (int i = 0; i < n; i++)
  {

If any element of the array is greater than $s_{0}$ s_0, such a split is not possible.

    if (m[i] > s0) return 0;

Compute the sum of the current subarray.

    sum += m[i];

As soon as this sum exceeds the value $s_{0}$ s_0, increase the subarray counter $c n t$ by $1$ and start accumulating the sum for the next subarray.

    if (sum > s0)
    {
      sum = m[i];
      cnt++;
    }
  }

If the array can be split into no more than $k$ subarrays, then it can also be split into exactly $k$ subarrays (since $k \leq n$ k \le n).

  if (cnt <= k) return 1;
  return 0;
}

The main part of the program. Read the input data. In the variable $r i g h t$ , compute the sum of all elements in the array.

scanf("%d %d", &n, &k);
left = 1; right = 0;
for (i = 0; i < n; i++)
{
  scanf("%d", &m[i]);
  right += m[i];
}

C++

The desired minimum value of the maximum subarray sum lies within the range $[l e f t; r i g h t]$ [left; right]. Perform a binary search on this interval.

while (left < right)
{
  mid = (left + right) / 2;
  if (f(mid) == 1)
    right = mid;
  else
    left = mid + 1;
}

C++

Print the answer.

printf("%lld\n", left);