Given an array of N elements, I need to split it into k subarrays, where k can be between 2 <= k <= N. A sub-array's score is determined by:
(left boundary point - right boundary point of the subarray)^2 max(subarray).
Left boundary point would be the index of the element and right boundary point would be the (index of the element 1) if that makes sense. You can think of them as points where you split the array.
Find an algorithm in O(n^2) that calculates the sum of the scores of all subarrays such that it is the lowest possible score obtained.
For example:
array = [5,3,4,9,2,8]
subarrays = [5,3], [4,9,2], [8]
score of the first subarray = (2-0)^2 (5) = 9
score of the second subarray = (5-2)^2 (9) = 18
score of the third subarray = (6-5)^2 (8) = 9
sum of all the scores of all the subarrays = 36.
What I tried to do:
I tried to choose the partitions of the array such that: (left boundary point - right boundary point of the subarray)^2 < max(subarray) but also avoid k = N as they wont give me the lowest score (something i observed through trial and error).
but I am not sure if that is right way to go about it. Thanks!
CodePudding user response：
The approach I would take, in pseudo-code:
- Start calling a recursive function with a simple solution candidate: a list of one N subarray, with value V.
- You can split this up with first any smaller subarray with value v < V. The rest must be split for total value < V - v.
The splitting up is pruned (candidates discarded) by v < V. This might be improved with some extra math. A subarray of 1 element x has value x. So v x < V for the for a one smaller subarray.
The complexity is indeed O(N^2), as the value calculation for the next larger subarray is based on prior max, both prior boundaries and the new element.
The actual coding I won't spoil for you.
The value calculation needs some thought (prior max, boundaries) and the splitting. The latter I would start with a List<int[]> but it can be done smarter, like using a BitSet.
I could not fit your ideas into this top-down (=recursive) approach. But who knows.
CodePudding user response：
Dynamic programming can do this in O(N^2). Since this is probably homework, I won't give you code.
I will start with a simpler problem, which is how to solve this for 1 <= k <= N.
As always, dynamic programming can be done either top down or bottom up. Usually it is easier to do recursive then memoize, which is top down. But your score function makes bottom up easier in this case.
What we want to do is wind up with an array of, by starting length, the best solution. The starting array is [5,3,4,9,2,8]. We begin with:
best = []
Next we want the min of:
score of [5] = (5-5)**2 5 = 5
So we get:
best = [5]
Next we want to append the min of:
best[0] score of [3] = 5 (3-3)**2 3 = 8
score of [5, 3] = (5-3)**2 5 = 9
So we get:
best = [5, 8]
Next we want to append the min of:
best[1] score of [4] = 8 (4-4)**2 4 = 12
best[0] score of [3, 4] = 5 (3-4)**2 4 = 10
score of [5, 3, 4] = (4-5)**2 5 = 6
So we get:
best = [5, 8, 6]
And so on until we get:
best = [5, 8, 6, 15, 15, 16]
But there is a problem. That 16 represents the minimum of:
best[4] score of [8]
best[3] score of [2, 8]
best[2] score of [9, 2, 8]
best[1] score of [4, 9, 2, 8]
best[0] score of [3, 4, 9, 2, 8]
score of [5, 3, 4, 9, 2, 8]
That very last entry is a solution with k=1. So you have to recalculate the last min correctly to be sure of the answer. (In this case it is the answer because 16 corresponds to the split [5, 3, 4], [9, 2, 8], but you have to check.)
If you implement this in the simplest way you'll get a O(n^3) algorithm because those score of ... operations require calculating a sublist, looking at its endpoints, and finding the max. There are O(n^2) such calculations, and finding the sublist and finding the max are potentially O(n). But if you're slightly clever about keeping running totals of the max and not actually generating those sublists every time, then you can get down to O(n^2).