Как мы можем заверить, что битоническая последовательность будет сформирована из одной самой длинной возрастающей подпоследовательности и одной самой длинной уменьшающейся подпоследовательности?

Например, у нас есть array[]={1,3,2,7,4,6,8,9}.Как мы можем заверить, что битоническая последовательность будет сформирована из одной самой длинной возрастающей подпоследовательности и одной самой длинной уменьшающейся подпоследовательности?

Самая длинная возрастающая подпоследовательность этого array[]={1,3,4,6,8,9} и его длина = 6.

самая длинная убывающая подпоследовательность этого array[]={3,2} и его длина = 2.

А это битоническая подпоследовательность этого array[]={1,3,4,6,8,9}? если да, то его длина = 6. Но длина битонической подпоследовательности = длина lis + длина lds -1, здесь они не равны. не

, если нет, как вы можете доказать, что длина bitonic подпоследовательности = длина лилией + длина ЛДС-1

Поправьте меня, если я ошибаюсь. Спасибо.

источник

2015-05-29 Varun Teja

Я думаю, что вам не хватает того, что длина биттонной подпоследовательности должна быть «length of lis» + «length of lds» - «количество элементов, которые появляются в обоих lis и lds». Кроме того, не должна ли ваша биттоническая подпоследовательность включать «2» из lds? – twalberg

@twalberg Учитывая массив A [0 ... n-1], содержащий n положительных целых чисел, подмассиво A [i ... j] является битоническим, если существует ak с i <= k <= j такое, что A [i] <= A [i + 1] ... <= A[k] > = A [k + 1]> =. A [j - 1]> = A [j]. . Я нашел это от geeksforgeeks, так как можно включить 2. –

Формула правильная и выдает 6 только ... Рассмотрим LIS [] (как массив LIS) и LDS [] (как массив LDS). Теперь, когда вы повторяете слева направо, вы достигаете позиции где LIS [index] = 6, то есть LIS до массива [7] равен 6. Теперь LDS [index = 7] равен 1 (тривиально один элемент является максимальной длиной ряда) ... NOW LIS [7] + LDS [7 ] -1 = (6 + 1-1)

Теперь доказательство, которое вы хотели для битной последовательности ... LIS [i], LDS [i] представляет собой самую длинную последовательность увеличения/уменьшения до i! Теперь, в конце концов, вы хотите максимизировать его, поэтому вы ищете образец пространства! Таким образом, ответ будет максимальным (LIS [i] + LDS [i] -1) 0 < = i < = n-1 ... Это -1 связано с повторным включением элемента в i-ое положение!

источник

2015-06-02 09:28:21

ответ

Смежные вопросы