Задача для прокачки мозгов (IQ) [требует правки]

Долго уже пытаюсь решить эту задачу. Надеюсь вы решите ее.

Имеется массив с положительными элементами (N элементов). Районном называется отрезок (l, r) (использовать нужно K районов, ни меньше ни больше), а его полезностью сумма всех элементов входящих в него из массива.

Нужно разделить массив на районы так, чтобы квадрат разности полезности всех районов был минимален. Отрезки не могут пересекаться, а также каждый элемент должен входить в один район.

N и K (1 ≤ N ≤ 500, 1 ≤ K ≤ 100, K ≤ N) соответственно, время 1 сек

Например: 1 2 3 4 5 6. Отрезки: 1 2 3 4 (1 до 4) и 5 6 (5 до 6), разность будет -1, а квадрат 1.

Сам сделал перебор, но по времени ни как не пройдет при максимальном N и K. Поэтому прошу вас помочь в решении. Необязательно давать решение задачи, можно дать теорию которую можно почитать чтобы решить или улучшить решение этой задачи. Я новичок в программировании, поэтому хочется изучать как все работает. Заранее спасибо!