# is there an O(n^2) approach to this problem?

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!

• The term "left boundary point" is unclear, and it is not helped by the fact that your example does not give an optimal solution (as [5,3,4], [9,2,8] would have a score of $9 + 5 + 9 + 9 = 32$ if I have correctly understood what you are trying to do). Nov 5, 2022 at 5:31
• Also that looks typically like something that can be solved using dynamic programming. Nov 5, 2022 at 5:38
• @Nathaniel 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. Nov 5, 2022 at 5:41
• @Nathaniel 32 would be correct as long as it is the lowest score we obtain Nov 5, 2022 at 5:51
• I think length after trying to understand left boundary point - right boundary point. Nov 5, 2022 at 6:50

Dynamic programming gives an $$O(n^2)$$ solution. Consider partitioning the array recursively to compute the scores of each possible partition. In particular, notice that

$$OPT([a_1, ..., a_n]) = \min_t \text{score}([a_1, ..., a_t]) + OPT([a_{t+1}, ..., a_n])$$

This naturally leads us to a recursive approach.

min_partition(arr, index):
if index == len(arr) - 1:
return 1 + arr[-1]
if dp[index] != max_int:
return dp[index]
score = max_int
for i in range(index+1, len(arr)):
score = min(score, (index-i)**2 + max(arr[index:i]) + min_partition(arr, i))
dp[index] = score
return score



As a slight optimization to Nathaniel's answer, a pre-processed data structure such as a sparse table can be created in $$O(n \log(n))$$ time and queried in $$O(1)$$ time to obtain $$\max$$ of any range. Asymptotically, however, the algorithm is still $$O(n^2)$$ since we solve each subproblem exactly once and each subproblem takes $$O(n)$$ time to solve. In particular,

$$T(n) = \sum_{i=1}^n i = \frac{n(n+1)}{2} = O(n^2)$$ (p.s. this is my first post, so I'd love feedback on how I can improve as a contributor!)

• thank you so much, your answer was clear and thorough! Nov 6, 2022 at 10:25

Given an array $$A = [a_0, …, a_{N-1}]$$, let us define some notations:

• for $$0\leqslant i < j \leqslant N$$, $$M_{ij}$$ is the maximum element in $$[a_i, a_{i+1}, …, a_{j-1}]$$;
• for $$0 < j \leqslant N$$, $$S(j)$$ is the minimum total score of a splitting of $$[a_0, …, a_{j-1}]$$ into subarrays (with no condition on the number of subarrays);
• for $$0 \leqslant i < j \leqslant N$$, $$T(i, j)$$ is the minimum total score of a splitting of $$[a_0, …, a_{j-1}]$$ into subarrays, with the last subarray being $$[a_i, …, a_{j-1}]$$.

First, notice that a matrix containing the values $$M_{ij}$$ can be computed in $$\mathcal{O}(N^2)$$ time. Then, find relations to compute:

• $$T(j, j+1)$$ given $$S(j)$$;
• $$T(i, j + 1)$$ given $$T(i, j)$$, for $$i < j$$;
• $$S(j+1)$$ given $$T(0, j+1)$$, $$T(1, j+1)$$, …, $$T(j, j+1)$$

And then find a way to compute all this in $$\mathcal{O}(N^2)$$ time. The minimum possible score can be expressed using the above values, can you see how?

After that, an algorithm computing this score can be easily modified to find the splitting to obtain this score.

Very simple via dynamic programming (which is just a big name for a very simple principle).

If you have one single array element, you have no choice but taking that element as the only subarray.

If you have k ≥ 2 array elements, then you can take all k elements as the only subarray. Or you take 1 element as the last subarray and the first k-1 elements optimally arranged into subarrays. Or you take 2 elements as the last subarray and the first k-2 elements optimally arranged into subarrays. Or you take 3 elements as the last subarray and the first k-3 elements optimally arranged into subarrays. And so on until you try taking the last k-1 elements as the last subarray and the first element optimally arranged into subarrays.

There are k choices, and you take the best choice. You do this for k = 2, k = 3, k = 4, and so on until k = n, and then you are done. For each k, you store the total cost of the optimal split into subarrays, and the length of the last subarray in the optimal split, so you can easily output the total cost of all items and how to split them.

Since calculating the best cost for each of these cases is constant in time, and there are about n^2/2 cases to consider, the time is quadratic.

However, in many cases you can do a lot better than O(n^2). For example, if you try to find out how to best arrange the k first items when you know how to do the k-1 first, and item #k has a value of 10, then you won't make that item part of a subarray with six or more elements: If you did, then turning it into a one-item subarray (cost 10 + 1^2 = 11) and reducing the size of a six item subarray by one (savings 6^2 - 5^2 = 11) means you never use a six item subarray at the end, and only check 5 cases instead of k. For item #k calculate min (k, value / 2), let s be the sum of all these values, and you can solve the problem in O(s).

You will probably be able to make similar savings if you have very large values, except instead of splitting subarrays you will try to join them, because that way a very large second-largest value doesn’t count anymore. Say you have thousand items, and two items with largest values 2,000,000 and 1,500,000. They must be in the same subarray, because then the total cost is at most 2,000,000 + 1000^2 instead of at least 2,000,000 + 1,500,000.