Dynamic Programming

This is in C.

Say I give you a sequence of numbers, for example 1 2 5 -2 5 2 -4 8.  Each number is a reward. Pick the sequence of numbers that will maximize your reward, with minimum of n spaces between numbers, and maximum m spaces between numbers. The minimum doesn't apply at the beginning and end of your sequence.  So for the above sequence, if n=1 and m=3, the correct answer would be 1 _ 5 _ 5 _ _ 8

How does one maximize the reward?

hello, ``eye''

still can't do your homework?

The clue is in the topic, use dynamic programming. The idea behind dynamic programming is that you divide the problem into a bunch of smaller subproblems, and then combine their results to get the final solution. Thus you should recursion to find the numbers that yield the highest reward with the space restrictions.

My advice would be to go from left to right on the numbers, and recursively call a function that will give the sequence with the highest reward. So forexample if we want to see which sequence that starts with 1 has the highest reward, then we create three new sequences, one with one space (replacing 2) one with two spaces( replacing 2 and 5) and one with three spaces(replacing 2, 5, -2). Then send those sequences recursively back to the function and have them do the same. Then at the end when they are done running (can't go further) you count up their rewards and the final return from your recursive calls should have the sequence with the highest reward with 1 at the start.

bampu pantsu