Разделите массив на k смежных разделов так, чтобы сумма максимального раздела была минимальной.

Предположим, вы знаете ответ x, что означает, что сумма максимального подмножества равна x. Вы можете проверить это предположение с помощью жадного алгоритма O(n). (Проходите по массиву слева направо и выбирайте элементы, пока сумма этого подмножества не станет меньше, чем x). Теперь вы можете выполнять бинарный поиск по x и находить минимальное значение для x. Сложность этого алгоритма составляет O(nlogn).

Это пример бинарного поиска в демонстрационном пространстве.

int min_max_sum(std::vector<int> & a, int K) {        

    int n = a.size();    
    long long high = 0, low = 0, mid = 0;

    for (int i = 0; i < n; ++i) {
        high += a[i];
        low = max(a[i], low);
    }

    while(low <= high) {
        mid = (low+high)/2;

        long long part_sum = 0;
        int parts = 1;
        for (int i = 0; i < n; ++i) {
            if (part_sum + a[i] > mid) {
                part_sum = 0;
                parts++;
            } else {
                part_sum += a[i];
            }
        }

        // if no. of parts in less than (or equal to) K then mid needs to (,or can) be more constrained by reducing upper limit
        if (parts <= K) {
            high = mid - 1;
        } else { 
            low = mid + 1;
        }
    }

    return mid;
}

сложность: O(n log(сумма(массив))).

Но поскольку логарифмы экспоненциально лучше, чем линейные, эта сложность неплохая.

Сложность в наихудшем случае: O(n log(INT_MAX * n))=O(32 n +n log(n))=O(n log(n)).

Давайте начнем с примера. Предположим, что N=5 и k=3(при условии, что после деления будет три части). Пусть наш массив будет {1,2,8,4,9}. Мы можем заметить, что если k было равно 1, то сумма максимального раздела была бы суммой (все элементы массива), т.е. 24, а если k=5, то сумма максимальный раздел будет max(все элементы массива), т. е. 9. Теперь мы можем наблюдать, что по мере увеличения k сумма минимального значения максимального раздела уменьшается. В этом наш алгоритм воспользуется помощью бинарного поиска. Но как это сделать????? Глядя на вопрос, мы видим, что мы должны найти минимум максимума, который вызывает ощущение проблем типа «FFFFTTTTTTTT», где мы должны найти первое T. Мы собираемся сделать то же самое, но возьмем помощь функции в этом. (Посмотрите на код и ответьте здесь, параллельно). Вспомогательная функция найдет значение K, когда будет предоставлена ​​​​минимальная сумма максимального раздела. Мы инициализируем low = max (все элементы массива), здесь low=9 и high=sum(все элементы массива), т.е. high=24. Следовательно, mid=16, поэтому для min_max_dist=16 наша вспомогательная функция вернет необходимое количество k. k>K, это означает, что наш min_max_dist может вместить больше значений. Таким образом, мы увеличим наше минимальное значение до mid+1, и если количество k‹=K , это означает, что при меньшем количестве разделов мы можем достичь этого min_max_dist, но мы можем сделать больше разделов и, следовательно, мы можем уменьшить высокое значение до среднего. Итак, наш код будет выполняться в нашем примере в следующем примере. путь:-

    low           high               mid       number_of_k
    9             24                 16         9
    9             16                 12         2
    9             12                 10         4
    11            12                 11         3

и, наконец, будет возвращен наш результат->low=11..

    #include <bits/stdc++.h>
    #define ll long long int
    using namespace std;

    ll number_of_k(ll arr[],ll n,ll minimum_max__dist){
       ll sum=0;
       ll k=1;
       for(ll i=0;i<n;i++){
          sum+=arr[i];
         if(sum > minimum_max__dist){
           sum=arr[i];
            k++;
          }
      }
    return k;
   }

    ll Max(ll arr[], ll n)
    {
       ll max1 = -1;
       for (ll i = 0; i < n; i++)
          if (arr[i] > max1)
              max1 = arr[i];
      return max1;
    }

    ll Sum(ll arr[], ll n)
    {
      ll sum = 0;
       for (int i = 0; i < n; i++)
       sum += arr[i];
       return sum;
     }

       ll min_max_bin_search(ll arr[],ll n,ll k){
         ll low=Max(arr,n);
         ll high=Sum(arr,n);
         ll mid;
while(low<high){
     mid=low+(high-low)/2;
    if(number_of_k(arr,n,mid)<=k)
       high=mid;
    else
        low=mid+1;
     }
  return low;
  }


 int main()
 {
      ll n,k;
       cin>>n>>k;
       ll arr[n];
       for(ll i=0;i<n;i++)cin>>arr[i];
       cout<<min_max_bin_search(arr,n,k)<<endl;

   return 0;
 }

Временная сложность этого алгоритма равна->O(nlogn)

Прочтите эту статью о двоичном поиске-> https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/ и решить эту проблему-> http://www.spoj.com/problems/AGGRCOW/

Вы можете найти хорошую статью о решении на основе динамического программирования здесь: https://www.geeksforgeeks.org/painters-partition-problem/ и его сложность O(k*N^2).

Чтобы получить лучшее решение, вы можете использовать метод бинарного поиска, предложенный другими. Вы можете найти более подробное решение, использующее бинарный поиск, здесь: https://www.geeksforgeeks.org/painters-partition-problem-set-2/ и его сложность O(NlogN)

Это можно решить с помощью динамического программирования:

Определим первое DP[n,m] как оптимальное решение для разделения подмассива C[1..n] на m частей. Где каждая часть имеет хотя бы один элемент.

DP[n,1] = sum(C1:Cn)
DP[n,n] = max(C1:Cn)
DP[n,m] = min( sum(Ck:Cn) + DP[k-1,m-1] )
          where k goes from m to n

Объяснение:
DP[n,1] — Базовый случай, когда количество разделов равно 1, есть только один способ — оставить все элементы (от 1 до n).
DP[n,n] — При любом количестве разделов равны количеству элементов, оставшихся в массиве, существует только один законный способ его разделить — каждый элемент в отдельном разделе, поэтому раздел с максимальной суммой является максимальным элементом в массиве.
DP[n,m] — это основное решение. Мы точно не знаем, сколько элементов будет у нас следующим разделом, поэтому нужно перебрать все варианты и получить от него минимум.

Разделение — это просто проблема грубой силы. Вы должны сосредоточиться на функции, чтобы минимизировать. Итак, вам нужно свести к минимуму отклонение от среднего значения.

int sum_arr(int *arr,int size)
{
    int res=0;
    while (size-->0)
       res+=*arr++;
   return res;
}
int   minimize( const int *array, int size)
{
    int i,j,cur_i;
    double dev, cur_min,avg=(double)sum_arr(array,size)/size;

    for (i=1;i<size-1;i++)
      {
         dev=abs(avg-sum_arr(array,i));
         dev+=abs(avg-sum_arr(array+i,size-i);
         if (dev<cur_min)
         {
              cur_min=dev;
               cur_i=i;
         }
      }
     return cur_i;
}

Простой код будет: (не проверено)