Как найти возрастающую подпоследовательность чисел с максимальной суммой?

Question

Как найти возрастающую подпоследовательность чисел с максимальной суммой.Я нахожу O (N ^ 2), но я хочу знать O (N log N).

Спасибо!

Answer 1

Я предполагаю:

• Вам совершенно не важна длина подпоследовательности.
• Подпоследовательности не должны быть смежными

Это составляет мир разницы!

---

Решение

Пусть оптимальное множество S извозрастающие подпоследовательности (IS) для массива A представляют собой набор IS, такой, что для каждого IS s в A мы имеем ровно одно из:

• s в в S
• В S есть IS s', такой что
  • sum(s')> = sum(s) и
  • largest_element(s') <= <code>largest_element(s)

Оптимальный набор S может быть упорядочен как по наибольшему элементу подпоследовательностей, так и по их сумме - порядок должен быть одинаковым.Это то, что я имею в виду под наименьшей / наибольшей последовательностью позже.

Наш алгоритм должен затем найти оптимальный набор A и вернуть его наибольшую последовательность.S можно вычислить следующим образом:

S := {[]} //Contains the empty subsequence
for each element x in A:
   s_less := (largest sequence in S that ends in less than x)
   s := Append x to s_less
   s_more := (smallest sequence in S that has sum greater than s)

   Remove all subsequences in S that are between s_less and s_more 
    (they are made obsolete by 's')

   Add s to S

Самая большая подпоследовательность в S является самой большой подпоследовательностью в массиве.

Каждый шаг может быть реализован в O (log n), если S является сбалансированнымбинарное дерево.N шагов дают O (n * log n) общей сложности.

Предостережение: вполне вероятно, что в моем псевдокоде может быть несколько ошибок + - 1 - их нахождение оставлено читателю в качестве упражнения.:)

---

Я постараюсь привести конкретный пример .Может быть, это поможет прояснить идею.Подпоследовательность, расположенная справа, всегда самая лучшая, но остальные - потому что в будущем они могут вырасти до самой тяжелой последовательности.

curr array | Optimal Subsequences
[]              []

//best this we can do with 8 is a simgleton sequence:
[8]             [] [8]

//The heaviest sequence we can make ending with 12 is [8,12] for a total of 20
//We still keep the [8] because a couble of 9s and 10s might make it better tahn 8+12
[8,12]          [] [8] [8,12]

[8,12,11]       [] [8] [8,11] [8,12]
[8,12,11,9]     [] [8] [8,9] [8,11] [8,12]

//[8,9,10] makes [8,11] and [8,12] obsolete (remove those).
//It not only is heavier but the last number is smaller.
[8,12,11,9,10]  [] [8] [8,9] [8,9,10]

Answer 2

Сканирование массива.Поддерживать дерево отображения, отображающее каждый элемент x на максимальную сумму подпоследовательности, заканчивающейся на x.Это splay-дерево сортируется по x (не по индексу x), и каждый узел украшен максимумом поддерева.Первоначально дерево содержит только бесконечный бесконечность => 0. Чтобы обработать новое значение y, найдите в дереве самое левое значение z, такое что y <= z.Splay Z в корень.Поддерево max M левого дочернего элемента z - это максимальная сумма подпоследовательности, которую может расширить y.Вставьте (y, M + y) в дерево.В конце верните дерево макс. </p>

Answer 3

Я столкнулся с похожим вопросом о codeforces.Проблема может быть решена с использованием деревьев сегментов с координатным сжатием или с использованием сбалансированных бинарных деревьев поиска.Обратитесь к ссылкам ниже для подробного объяснения.

последовательность увеличения максимальной суммы

После прочтения вы можете попробовать этот вопрос о codeforces.

Answer 4

1.) Сортировать подпоследовательность

2.) Итерация по списку, добавление следующего элемента к предыдущему элементу

3.) Как только вы достигнете двух элементов, чьи суммы больше, чем Maximum_sum, остановитесь. Все предыдущие могут быть объединены в <= Maximum_Sum. </p>

Предполагается, что вы просите добавить два элемента, чтобы сделать Maximum_sum. Общая концепция может быть обобщена для суммирования 0-N, где N - длина ваших «чисел». Однако вы не уточнили, что вы на самом деле складываете вместе, поэтому я сделал предположение. Кроме того, я не уверен, что это даст вам «ПОСЛЕДНЮЮ» подпоследовательность чисел, но это даст вам подпоследовательность чисел в N log N.

Это был вопрос для интервью, который Amazon.com задавал мне, когда я выдирала себе кишки от пищевого отравления в первом раунде интервью. Я добрался до второго раунда интервью, и они, похоже, не хотели продвигаться дальше этого момента. Надеюсь, вы справитесь лучше, чем я, если это вопрос на собеседовании, поэтому мой ответ может быть не лучшим, но, надеюсь, это лучше, чем сказать, что у вас есть дубликат ...

Надеюсь, это поможет,

-Брайан Дж. Стинар-