Maximum sum of n intervals in a sequence

Question

I'm doing some programming "kata" which are skill building exercises for programming (and martial arts). I want to learn how to solve for algorithms like these in shorter amounts of time, so I need to develop my knowledge of the patterns. Eventually I want to solve in increasingly efficient time complexities (O(n), O(n^2), etc), but for now I'm fine with figuring out the solution with any efficiency to start.

The problem:

Given arr[10] = [4, 5, 0, 2, 5, 6, 4, 0, 3, 5]

Given various segment lengths, for example one 3-length segment, and two 2-length segments, find the optimal position of (or maximum sum contained by) the segments without overlapping the segments.

For example, solution to this array and these segments is 2, because:

{4 5} 0 2 {5 6 4} 0 {3 5}

What I have tried before posting on stackoverflow.com:

I've read through:

Algorithm to find maximum coverage of non-overlapping sequences. (I.e., the Weighted Interval Scheduling Prob.)

algorithm to find longest non-overlapping sequences

and I've watched MIT opencourseware and read about general steps for solving complex problems with dynamic programming, and completed a dynamic programming tutorial for finding Fibonacci numbers with memoization. I thought I could apply memoization to this problem, but I haven't found a way yet.

The theme of dynamic programming is to break the problem down into sub-problems which can be iterated to find the optimal solution.

What I have come up with (in an OO way) is

foreach (segment) {
    - find the greatest sum interval with length of this segment

This produces incorrect results, because not always will the segments fit with this approach. For example:

Given arr[7] = [0, 3, 5, 5, 5, 1, 0] and two 3-length segments,

The first segment will take 5, 5, 5, leaving no room for the second segment. Ideally I should memoize this scenario and try the algorithm again, this time avoiding 5, 5, 5, as a first pick. Is this the right path?

How can I approach this in a "dynamic programming" way?

Answer 1

If you place the first segment, you get two smaller sub-arrays: placing one or both of the two remaining segments into one of these sub-arrays is a sub-problem of just the same form as the original one.

So this suggests a recursion: you place the first segment, then try out the various combinations of assigning remaining segments to sub-arrays, and maximize over those combinations. Then you memoize: the sub-problems all take an array and a list of segment sizes, just like the original problem.

I'm not sure this is the best algorithm but it is the one suggested by a "direct" dynamic programming approach.

EDIT: In more detail:

The arguments to the valuation function should have two parts: one is a pair of numbers which represent the sub-array being analysed (initially [0,6] in this example) and the second is a multi-set of numbers representing the lengths of the segments to be allocated ({3,3} in this example). Then in pseudo-code you do something like this:

valuation( array_ends, the_segments):
    if sum of the_segments > array_ends[1] - array_ends[0]:
        return -infinity

    segment_length = length of chosen segment from the_segments
    remaining_segments = the_segments with chosen segment removed

    best_option = 0
    for segment_placement = array_ends[0] to array_ends[1] - segment_length:
         value1 = value of placing the chosen segment at segment_placement
         new_array1 = [array_ends[0],segment_placement]
         new_array2 = [segment_placement + segment_length,array_ends[1]]
         for each partition of remaining segments into seg1 and seg2:
             sub_value1 = valuation( new_array1, seg1)
             sub_value2 = valuation( new_array2, seg2)
             if value1 + sub_value1 + sub_value2 > best_option:
                  best_option = value1 + sub_value1 + sub_value2
    return best_option

This code (modulo off by one errors and typos) calculates the valuation but it calls the valuation function more than once with the same arguments. So the idea of the memoization is to cache those results and avoid re-traversing equivalent parts of the tree. So we can do this just by wrapping the valuation function:

memoized_valuation(args):
    if args in memo_dictionary:
         return memo_dictionary[args]
    else:
         result = valuation(args)
         memo_dictionary[args] = result
         return result

Of course, you need to change the recursive call now to call memoized_valuation.