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

---

Как я могу разделить круговой массив на k групп смежных элементов таким образом, чтобы разница между максимальной суммой и минимальной суммой была минимальной. Каждая группа имеет непрерывный элемент массива.
Например, если массив выглядит следующим образом.
[6 13 10 2] и k=2, то o/p должно быть 18(6+10+2)-13=5. Поскольку массив является круговым, 6,10,2 являются смежными элементами массива.

Например, если массив выглядит следующим образом.
[6 13 2 10] и k=2, то o/p должно быть 16(6+10)-15(13+2)=1. Поскольку массив является круговым, 6,10 являются смежными элементами массива.

Например, если массив выглядит следующим образом.
[100 92 133 201 34 34 34 94 108] и k=4, то группируйте следующим образом 208(108,100), 225(92,133), (201), 196(34,34,34,94) Итак, 225-196=29

Что я уже пробовал:

Ниже приводится грубое силовое решение этого вопроса. Как я могу это оптимизировать?

//#define MAX_POINT 6
#define ARR_SIZE 100
//#define K 4
#include <limits>
#include<stdio.h>
#include<iostream>
using namespace std;

int ai[]={6,13,2,10};


/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);

int finddifference(int a[], int sizeai, int g){
	int min = 16000;
	for(int i=0;i<sizeai;i++){
		int j=0,k=i;
		int min_g=16000;
		int max_g=-16000;
		int sum=0;
		while(j<g){
			int temp=a[j];
			while(temp){

				sum+=ai[k];
				k=(k+1)%sizeai;
				temp--;
			}
			if(sum<min_g)
				min_g=sum;
			if(sum>max_g)
				max_g=sum;
			sum=0;
			j++;
		}

		if((max_g-min_g)<min)
			min=max_g-min_g;
	}
	return min;
}

/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n, int i, int max_point, int g, int *min)
{

	/* array must be static as we want to keep track
	of values stored in arr[] using current calls of
	printCompositions() in function call stack*/
	static int arr[ARR_SIZE];

	if (n == 0 && i==g)
	{
		int temp_min = finddifference(arr, max_point+g-1, g);
		*min = (temp_min<*min)?temp_min:*min;
		//printArray(arr,i);
	}
	else if(n > 0)
	{
		int k;
		for (k = 1; k <= max_point; k++)
		{
			arr[i]= k;
			printCompositions(n-k, i+1, max_point, g, min);
		}
	}
}

/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
	int i;
	for (i = 0; i < arr_size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

/* Driver function to test above functions */
int main()
{
	int n, g;
	cin>>n;
	cin>>g;
	int max_point=n-g+1;
	int min = 16000;
	printCompositions(n, 0, max_point,g,&min);
	cout<<"Answer"<<min<<endl;
	getchar();
	return 0;
}

---