Find an x amount of subarrays such that the total sum of those subarrays is minimum [closed]

Question

Find an x amount of non-overlapping and continuous subarrays such that the total sum of those subarray's is minimum, and the count of all elements are y.

Example 1:
Input: {2,1, 10, 40, 5, 6} , x=2, y=4
Output: {{2,1},{5,6}}

---

Example 2:
Input: {2,1, 10, 40, 5, 6} , x=1, y=2
Output: {{2,1}}

---

Example 3:
Input: {2,1, 10, 40, 5, 6} , x=1, y=3
Output: {{2,1,10}}

---

Example 4:
Input: {2,1, 10, 40, 5, 6} , x=1000, y=3
Output: {{2},{1},{5}} or {{2,1},{5}}

I have searched though the internet, but I couldn't find a similar problem. So, I made my own algorithm. Unfortunately the time complexity is exponential. I'm not going to give my solution, because I have created a tunnel vision and want to start from scratch with fresh ideas.

So, here is my question: Do you know an algorithm to solve this problem as efficient as possible?

Any help would be greatly appreciated!

P.S. As a reminder, don't underestimate the complexity of the problem.

Answer 1

Here's my try to apply the DP approach.

Let M(I, Y, X, L) be the the minimum total sum of subarrays where:

• I - we use the first I elements of the original array ARR
• Y - the count of all elements in the subarrays
• X - upper bound for number of subarrays
• L = 1 if the last (I-th) element is included in one of the subarrays forming the minimum value, otherwise L = 0

Then the following formulas apply:

M(I, Y, X, 1) = ARR[I] + MIN(M(I-1, Y-1, X, 1), M(I-1, Y-1, X-1, 0))

and

M(I, Y, X, 0) = MIN(M(I-1, Y, X, 1), M(I-1, Y, X, 0))