here is a (shortened) question from one of my old national olympiad

given N and K and an array of N integers 1 and 10^6 inclusive.

partition the array into exactly K subarrays and calculate their sum. find the minimum possible difference of the maximum sum and the minimum sum.

(1<k<=n<=40)

for example for N=6 and K=3 and array={5 1 1 1 3 2}

the optimal way is to split it into [5][1 1 1][3 2] so the maximum sum is 5, minimum sum is 3 so the answer is 5-3=2.

i think the right step is to use prefix sum so pref[i] -> sum of element from 1..i

i thought about DP[pos][k][lmin][rmin][lmax][rmax] where it means the answer for subarray 1..pos where we already made k subarray and the subarray with minimum sum is in lmin..rmin and the subarray with maximum sum is in lmax..rmax. transition is O(n) so the complexity is O(n^7)

i also have an idea of fixing Lmin,Rmin,Lmax,Rmax (O(n^4)) and find if we can get K-2 subarrays from the remaining elements with the sum between (pref[Rmin]-pref[Lmin-1]) and (pref[Rmax] — pref[Lmax-1]). but i need an O(n) way to do that but it seems i cant find one (think about a greedy strategy which moves from left to right and increase cnt whent the current sum is >=min and reset sum to 0. but it does not work the cnt>k because its not certain that we can split something and keep the sum>=mn

so can i have some hints for this problem?