Разделить массив на K подмассивов с минимальной разницей

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ:

Описанная проблема выглядит как задача из конкурса. Я не участвую ни в одном из них, я не знаю о каких-либо текущих соревнованиях, в которых может быть проблема. Если они есть, я закрою вопрос, чтобы оставаться честным!

У меня есть проблема: учитывая массив значений A и целое число K, разбить A ровно на K непересекающихся смежных подмассивов таким образом, чтобы разница между подмассивом с минимальной и максимальной суммами подмассива была минимальной. Разрешается вращать A на любое число в любом направлении.

Рассмотрим пример:

Вход: А = [5 1 1 1 3 2], К = 3

Вывод: [5][1 1 1][3 2], максимальная сумма = 5, минимальная сумма = 3, результат = 2

У меня есть частично работающий код (ужасно некрасивый, мой плохой, но это не означает, что он будет качественным):

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

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 = INT_MAX;
  // consider all possible rotations/shifts
  for(int offset = 0; offset < n; ++offset) {
    for(int l_min = 0; l_min < n; ++l_min) {
      for(int r_min = l_min; r_min < n; ++r_min) {
        // check minimal sum subarray
        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] = 0;
          }
        }
        // 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 = 0; l_max < n; ++l_max) {
            for(int r_max = 0; r_max < n; ++r_max) {
              int max_sum = sum(deps, l_max, r_max);

              if (max_sum >= min_sum) dp[p][r_max] = max(dp[p-1][l_max], max_sum);
            } // l_maxs
          } // r_maxs
        } // partitions
        // printing dp

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

        // update difference
        res = min (res, dp[k-1][n-1] - min_sum);
      } // end min sum seg
    } // start min sum seg
    //break;
  } // cuts
  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;
}

Идея проста: предположим, что текущий раздел имеет минимальную сумму, перечислите все возможные максимальные разделы, настройте динамическое программирование для получения максимальной суммы с минимальным значением, проверьте разницу. Общая сложность: O(K*N^4).

Моя проблема в том, что он не проходит некоторые тесты, и я застрял в устранении неполадок. Может ли кто-нибудь помочь мне с этим?

Неудачный тест, например:

N = 4, K = 2, A = [6 13 10 2]

ОБНОВИТЬ

Эта версия должна исправить некоторые предыдущие проблемы. Во-первых, он убирает ненужный цикл по «смещениям» и добавляет просто поворот массива в конце цикла l_min. Во-вторых, я заметил, что dp нельзя инициализировать 0 - это задача минимизации, поэтому его нужно инициализировать каким-то большим значением (зависит от констант задачи, max_value здесь уже вне области значений). Наконец, интервалы больше не должны перекрываться - каждая сумма исключает левый конец интервала. Тем не менее, это все еще не дает ожидаемых результатов.

#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 l_min = 0; l_min < n; ++l_min) {
    for(int r_min = l_min; r_min < n; ++r_min) {
      int min_sum = sum (deps, l_min+1, 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 = 0; 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] = 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

    // rotate an array to consider different starting points
    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;
}