Не увеличивающаяся и не убывающая подпоследовательность - PullRequest
Новая
       18

Не увеличивающаяся и не убывающая подпоследовательность

1 голос
/ 06 марта 2012

Нахождение неубывающей подпоследовательности является хорошо известной проблемой. Но этот Вопрос - небольшой вариант нахождения самой длинной неубывающей подпоследовательности. В этой задаче мы должны найти длину самой длинной подпоследовательности, которая состоит из 2 непересекающихся последовательностей: 1. неубывающей 2. не возрастающей. например В строке «aabcazcczba» самой длинной такой последовательностью является aabczcczba. aabczcczba состоит из 2 непересекающихся подпоследовательностей aabcZccZBA. (заглавная буква показывает не возрастающую последовательность)

Мой алгоритм 

length = 0
For i = 0 to length of given string S
  let s' = find the longest non-decreasing subsequence starting at position i
  let s" = find the longest non-increasing subsequence from S-s'.
  if (length of s' + length of s") > length
      length = (length of s' + length of s")
enter code here

Но я не уверен, даст ли это правильный ответ или нет. Можете ли вы найти ошибку в этом алгоритме, и если есть ошибка, также предложите правильный алгоритм. Также мне нужно оптимизировать решение. Мой алгоритм будет делать примерно o (n ^ 4) шагов.

Ответы [ 2 ]

1 голос
/ 06 марта 2012

Ваше решение определенно неверно. Например. addddbc. Самая длинная неубывающая последовательность - это adddd, но это никогда не даст вам нерастущую последовательность. Оптимальным решением является abc и dddd (или ab ddddc, или ac ddddb).

Одним из решений является использование динамического программирования.

F (i, x, a, b) = 1, если существует неубывающая и не возрастающая комбинация из первых i букв x (x [: i]) такая, что последняя буква неубывающей части является, а не увеличивающаяся часть является б. Обе эти буквы равны NULL, если соответствующая подпоследовательность пуста.

В противном случае F (i, x, a, b) = 0. 

F(i+1,x,x[i+1],b) = 1 if there exists a and b such that 
    a<=x[i+1] or a=NULL and F(i,x,a,b)=1. 0 otherwise.

F(i+1,x,a,x[i+1]) = 1 if there exists a and b such that
    b>=x[i+1] or b=NULL and F(i,x,a,b)=1. 0 otherwise. 

Initialize F(0,x,NULL,NULL)=1 and iterate from i=1..n

Как видите, вы можете получить F (i + 1, x, a, b) из F (i, x, a, b). Сложность: линейная по длине, полиномиальная по размеру алфавита.

0 голосов
/ 11 марта 2012

Я получил ответ, и вот как это работает, благодаря @ ElKamina

поддерживает таблицу размера 27X27.27 = (1 нулевой символ + 26 (алфавиты)) таблица [i] [j] обозначает длину подпоследовательности, у которой неубывающая подпоследовательность имеет последний символ «i», а не возрастающая подпоследовательность имеет последний символ «j» (0-й индекс обозначаетнулевой символ и k-й индекс обозначают символ 'k')

для i = 0 до длины строки S 

  //subsequence whose non decreasing subsequence's last character is smaller than S[i], find such a subsequence of maximum length. Now S[i] can be part of this subsequence's non-decreasing part.

  int lim = S[i] - 'a' + 1;
  for(int k=0; k<27; k++){
    if(lim == k) continue;
    int tmax = 0;
    for(int j=0; j<=lim; j++){
      if(table[k][j] > tmax) tmax = table[k][j];
    }
    if(k == 0 && tmax == 0) table[0][lim] = 1;
    else if (tmax != 0) table[k][lim] = tmax + 1;
  }
 //Simillarly for non-increasing subsequence

Сложность по времени равна o (lengthOf (S) * 27 * 27) икосмическая сложность o (27 * 27)

...