algorithm for series to calculate the maximum descend inside?

Question

Given a series x(i), i from 1 to N, let's say N = 10,000.

for any i < j,
D(i,j) = x(i) - x(j), if x(i) > x (j); or,
       = 0, if x(i) <= x(j).

Define

Dmax(im, jm) := max D(i,j), for all 1 <= i < j <=N.

What's the best algorithm to calculate Dmax, im, and jm?

I tried to use Dynamic programming, but this seems is not dividable... Then i'm a bit lost... Could you guys please suggest? is backtracking the way out?

Answer 1

Iterate over the series, keeping track of the following values:

• The maximum element so far
• The maximum descent so far

For each element, there are two possible values for the new maximum descent:

• It remains the same
• It equals maximumElementSoFar - newElement

So pick the one which gives the higher value. The maximum descent at the end of iteration will be your result. This will work in linear time and constant additional space.

Answer 2

If I understand you correctly you have an array of numbers, and want to find the largest positive difference between two neighbouring elements of the array ?

Since you're going to have to go through the array at least once, to compute the differences, I don't see why you can't just keep a record, as you go, of the largest difference found so far (and of its location), updating as that changes.

If your problem is as simple as I understand it, I'm not sure why you need to think about dynamic programming. I expect I've misunderstood the question.

Answer 3

Dmax(im, jm) := max D(i,j) = max(x(i) -x(j),0) = max(max(x(i) -x(j)),0)

You just need to compute x(i) -x(j) for all values , which is O(n^2), and then get the max. No need for dynamic programming.

Answer 4

You can divide the series x(i) into sub series where each sub series contains and descending sub list of x(i) (e.g if x = 5, 4, 1, 2, 1 then x1 = 5, 4, 1 and x2 = 2, 1) and then in each sub list you can do: first_in_sub_series - last_sub_series and then compare all the results you get and find the maximum and this is the answer.

If i understood the problem correctly this should provide you with a basic linear algorithm to solve it.

e.g:

x = 5, 4, 1, 2, 1 then x1 = 5, 4, 1 and x2 = 2, 1
rx1 = 4
rx2 = 1

dmax = 4 and im = 1 and jm = 3 because we are talking about x1 which is the first 3 items of x.