Dividing array so sum of subarray maximums is minimised

I can only think of a brute force way to solve this. Interested to see what Algo SO community would come up with.

Giving an arr a and an integer x (1<x<=len(a)). Wihout reordering the array divide the array into x subarrays s1, s2....sx such that the sum of max(s1) + max(s2)....+ max(sx) is the minimum out of all possible combinations of sum of subarrays (see example below). return an array with x-1 indexes containing the index i (not inclusive) where the split happens a[0:i], a[i+1:i2], a[i2+1: i3].....a[ix:].

Example:

a = [10,30,40,20,50]  x = 2  return = [1]  

splitting the array at index 1 into [10] and [30,40,20,50]

would result max([10]) + max([30,40,20,50]) = 60 which is the minimum out of all other ways to split array.

other possible splits -

• cannot split at index 0 because then it would only result in 1 array and x = 2
• split at index 2 = max([10,30]) + max([40,20,50]) = 80
• split at index 3 would result 90
• split at index 4 would result 90
• split at index 5 not allowed because then it would only result in 1 array and x = 2

https://stackoverflow.com/questions/65416097/dividing-array-so-sum-of-subarray-maximums-is-minimised December 23, 2020 at 05:35AM