Алго: Унимодальная полоса

Question

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

, то есть:в векторе [4 5 8 5 9 6 3] 45863 является унимодальной полосой, а 458593 - не потому, что увеличивается до 8, затем уменьшается до 5, а затем снова увеличивается (что недопустимо).

Использование динамическогоПрограммирование Мне удалось создать 3 вектора: первый с длиной самой длинной убывающей полосы, которая останавливается на элементе x, второй с длиной самой длинной убывающей полосы, начинающейся с элемента x, а третий -сумма первых двух.

В основном, если я возьму максимум третьего вектора, это длина самой длинной унимодальной полосы + 1 (потому что элемент x считается дважды).

Что яхочу сделать сейчас, чтобы отобразить эту полосу.Я думаю об использовании этих векторов таким образом: используя «для», начиная с позиции максимума и переходя к началу вектора.Я собираюсь проверить значение в первом векторе, и если это значение будет на 1 меньше предыдущего значения (в первый раз это будет значение максимума в первом векторе), я сохраню это значение в очереди.и отобразите его позже, затем продолжите.Затем я сделаю почти то же самое для второй части вектора, используя второй вектор.

Я знаю, это звучит грязно и сложно, но с этим примером это будет понятнее.

I have this base vector :  
9 4 5 6 9 7 8 3 4 3

1 1 2 3 4 4 5 1 2 1 (first vector) = A
4 2 3 3 4 3 3 1 2 1 (second vector) = B
5 3 5 6 8 7 8 2 4 2 (sum of the two) = C

Итак, самая длинная полоса здесь - 7, а пик - 9 (или 8, но это одно и то же).

Итак, я хочу сделать следующее: значение пика «4» в первом векторетак что я проверю первое «3» влево, это 6 , я поставил его в очередь, теперь я ищу первое «2», это 5 в очереди, а затем это 4 , потому что это первое со значением "1".

Затем я выведу очередь, затем пик, затем сделаю то же самое со второй частью.У меня будет 4 5 6 9 7 4 3. (Какова хорошая последовательность).

Мой вопрос: будет ли это работать каждый раз?У меня такое чувство, что что-то может испортиться, поэтому я провел несколько тестов, и каждый раз все шло нормально.Я хотел бы знать, есть ли конкретные базовые векторы, которые все испортили.Пожалуйста, скажите мне, что, по вашему мнению, было бы здорово!

Спасибо, что прочитали все это, я надеюсь, что кто-то может мне помочь.

Answer 1

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

Одно замечание, хотя

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

Я думаю, что вы действительно хотите здесь, это stack , а не очередь , учитывая, что последний элемент, который вы найдете, будет первым, который вы хотите отобразить.Это относится к первому вектору.

В более общем случае вы можете использовать обычный массив, и это будет работать для обоих векторов.

Answer 2

Я думаю, что это звук.Если максимальный элемент лучшей унимодальной полосы равен e, то наилучшая возможная левая половина и правая половина будут найдены в A и B.Поскольку левая и правая последовательности полностью независимы, этот метод всегда будет работать.