Partition array in at most k subarrays that minimize a function I have 2 values \$N\$ and \$K\$ (\$1 \le K \lt N \le 1.000\$), where \$N\$ indicates a number of values (\$0 \le \text{value}2 \le ... \le \text{value}N \le 1,000,000\$) to be read from input. The first value isn't on the input and will always be 0.

All \$N\$ values need to be organized on at most \$K\$ groups where the sum of the groups size is minimized.

The size of a group is defined by the distance between the two most distant values in the group (MAX_VALUE - MIN_VALUE). If the group consists of only one value, its size is zero.

What is the minimum total value for the sum of the groups size if the values are organized optimally?

Here is an input sample:


5 2
1 2 5 6



Output sample:


3



My solution is a brute force search. This is a known problem. How can I do better than this solution?

#include &lt;cstdio&gt;
#include &lt;queue&gt;
#include &lt;vector&gt;
#include &lt;limits&gt;
#include &lt;algorithm&gt;

using groups = std::vector&lt; std::vector&lt;int&gt; &gt;;

int getTotalGroupsSize(groups &amp;g){
    unsigned long k = g.size();

    int total = 0;

    for (unsigned long i = 0; i &lt; k; ++i) {
        int max = std::numeric_limits&lt;int&gt;::min();
        int min = std::numeric_limits&lt;int&gt;::max();

        std::vector&lt;int&gt; &amp;subGroup = g[i];

        for (int j = 0; j &lt; subGroup.size(); ++j) {
            max = std::max(max, subGroup[j]);
            min = std::min(min, subGroup[j]);
        }

        total += (max - min);

    }


    return total;
}

int getOptimallSum(std::queue&lt;int&gt; &amp;q, groups &amp;g){

    if(q.empty())
        return getTotalGroupsSize(g);


    int front = q.front();
    q.pop();

    int minDiff = std::numeric_limits&lt;int&gt;::max();
    for (int i = 0; i &lt; g.size(); ++i) {
        g[i].push_back(front);
        minDiff = std::min(minDiff,getOptimallSum(q, g));
        g[i].pop_back();
    }

    q.push(front);
    return minDiff;
}


int main(void){
    int n,k;

    while (scanf("%d",&amp;n) != EOF) {
        scanf("%d",&amp;k);

        std::queue&lt;int&gt; q;
        q.push(0);
        for (int i = 1; i &lt; n; ++i) {
            int value;
            scanf("%d",&amp;value);
            q.push(value);
        }

        if(k &gt;= n){
            puts("0");
            continue;
        }

        groups g(k);
        printf("%d\n",getOptimallSum(q,g));

    }
    return 0;
}
Yes there is a better way.

The key observation is that since the array is sorted, the size of partition [p,q] is \$a_q - a_p\$, and the sum of sizes is almost \$a_N - a_1\$. Missing are gaps between right end of one partition and left end of the next one.

So the solution is to compute the set of sequential differences, and select \$K-1\$ largest. These are optimal partition points.

Otherwise, the code is clean and understandable.