Алгоритм для ряда для расчета максимального спуска внутри?

Question

Для ряда x (i), i от 1 до N, скажем, N = 10000.

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

Определить

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

Какой лучший алгоритм для вычисления Dmax,я, и jm?

Я пытался использовать динамическое программирование, но это, кажется, не делится ... Тогда я немного растерялся ... Не могли бы вы, ребята, предложить?возвращается назад?

Answer 1

Итерация по серии, отслеживание следующих значений:

• Максимальный элемент до сих пор
• Максимальный спуск пока что

Для каждого элемента есть два возможных значения для нового максимального спуска:

• Остается прежним
• Это равно maximumElementSoFar - newElement

Итак, выберите тот, который дает более высокое значение. Максимальный спуск в конце итерации будет вашим результатом. Это будет работать в линейном времени и постоянном дополнительном пространстве.

Answer 2

Вы можете разделить ряды x (i) на подсерии, где каждая подсерия содержит и нисходящий подсписок x (i) (например, если x = 5, 4, 1, 2, 1, то x1 = 5, 4, 1 и x2 = 2, 1), а затем в каждом подсписке вы можете сделать: first_in_sub_series - last_sub_series, а затем сравнить все полученные результаты и найти максимум, и это ответ.

Если я правильно понял проблему, это даст вам базовый линейный алгоритм для ее решения.

например:

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

dmax = 4 и im = 1 и jm = 3, потому что мы говорим о x1, который является первыми 3 элементами x.

Answer 3

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

Вам просто нужно вычислить x (i) -x (j) для всех значений, то есть O (n ^ 2), а затем получить макс.Нет необходимости в динамическом программировании.

Answer 4

Если я правильно вас понял, у вас есть массив чисел, и вы хотите найти наибольшую положительную разницу между двумя соседними элементами массива?

Поскольку вам придется хотя бы один раз пройтись по массиву, чтобы вычислить различия, я не понимаю, почему вы не можете просто вести запись самой большой разницы, обнаруженной до сих пор (и его местоположения), обновляя при этом изменения.

Если ваша проблема настолько проста, насколько я понимаю, я не уверен, почему вам нужно подумать о динамическом программировании. Я полагаю, что неправильно понял вопрос.