CODEWITHSUNDEEP
arraysalgorithmdynamic-programming
Devos50
Devos50

Reputation: 2035

Getting N minimal contiguous blocks in an array of numbers

I'm currently working on the following problem:

Given an array of M positive numbers, I need to get N blocks of contiguous numbers with some given length. For example, when I have the array:

6 9 3 2 8 1 6 9 7

When I need to find one block of length 3, the solution is [3,2,8] which has a total minimal sum of 13. When I need to find two blocks, the algorithm should give [3,2,8] and [1,6,9] since the sum of all elements in these blocks is minimal (29). It is given that the length of the sequence is always strictly larger than N times the length of a block (so there is always a solution).

I think this problem is solvable by using DP but I currently can't see how. I'm struggling to find a recurrent relation between the subproblems. Could anyone give me a hand here?

Thanks in advance!

Upvotes: 2

Views: 796

Answers (1)

Timothy
Timothy

Reputation: 4487

  1. Calculate the sum of each block with the given length, and record them with the initial index. This can be done by a complexity of O(n). So you get a list like:

    index    sum
0        18
1        14
2        13
...      ...

  2. Due to the objective blocks could not overlap with each other, so each difference of their indexes can not be less than the given length. So you need to apply a simple dynamic planning algorithm on the list you got.

    if the block length is l, list length is n(say the list S[n]), and you want to find m blocks, then the

    F(n,m,l) = min { F(n-i-l,m-1,l) + S[n-i] } (for i = 0 ~ n-(m-1)*l)

The complexity of this step is O(nm) where m is how many blocks you want.

Finally the complexity is O(nm). Let me know if you need more details.

Upvotes: 6

Related Questions