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
没有评论:
发表评论