Тяжелая возрастающая подпоследовательность

9

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

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

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

Примеры:

                    [] ->  0 ([])
                   [3] ->  3 ([3])
             [3, 2, 1] ->  3 ([3])
          [3, 2, 5, 6] -> 14 ([3, 5, 6])
       [9, 3, 2, 1, 4] ->  9 ([9])
       [3, 4, 1, 4, 1] ->  7 ([3, 4])
       [9, 1, 2, 3, 4] -> 10 ([1, 2, 3, 4])
       [1, 2, 4, 3, 4] -> 10 ([1, 2, 3, 4])
[9, 1, 2, 3, 4, 5, 10] -> 25 ([1, 2, 3, 4, 5, 10])
       [3, 2, 1, 2, 3] ->  6 ([1, 2, 3])

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


Асимптотически быстрый код выигрывает, с меньшим размером кода в байтах в качестве тай-брейка.

orlp
источник
Как вы планируете бороться с несравненной асимптотикой? Потенциально есть две важные переменные: длина последовательности и размер самого большого элемента в последовательности.
Питер Тейлор
@PeterTaylor В качестве асимптотики я выбираю длину последовательности. Ваше решение не должно принимать каких-либо ограничений на целые числа и, в частности, не зацикливать и не выделять память в зависимости от размера используемых чисел. Вам прощают, если ваш выбор языка имеет ограниченные целые числа, но вы не должны использовать этот факт в своем решении. Это удовлетворяет ваши проблемы?
Orlp
Частично. Теоретически возможно (хотя, вероятно, маловероятно), что факт, что сравнение двух неограниченных целых принимает размер, пропорциональный их логарифму, может иметь значение. Возможно, вы захотите разрешить базовые операции (сложение, сравнение, возможно, умножение) над целыми числами за O (1) раз.
Питер Тейлор
@PeterTaylor Является ли трансдихотомическая модель вычислений достаточно конкретной?
orlp
Кажется разумным.
Питер Тейлор

Ответы:

3

JavaScript (ES6) O(n log n)253 символа

function f(l){l=l.map((x,i)=>[x,i+1]).sort((a,b)=>a[0]-b[0]||1)
a=[0]
m=(x,y)=>x>a[y]?x:a[y]
for(t in l)a.push(0)
t|=0
for(j in l){for(i=(r=l[j])[1],x=0;i;i&=i-1)x=m(x,i)
x+=r[0]
for(i=r[1];i<t+2;i+=i&-i)a[i]=m(x,i)}for(i=t+1;i;i&=i-1)x=m(x,i)
return x}

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

в основном, в базовом массиве типа данных каждое место сопоставляется с элементом из входного списка в том же порядке. дерево Фенвика везде инициализируется 0.

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

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

тогда мы просто возвращаем максимум всего дерева - это результат.

проверено на firefox

гордый хаскеллер
источник
4

Python, O (n log n)

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

import bisect
import blist

def heaviest_subseq(in_list):
    best_subseq = blist.blist([(0, 0)])
    for new_elem in in_list:

        insert_loc = bisect.bisect_left(best_subseq, (new_elem, 0))

        best_pred_subseq_val = best_subseq[insert_loc - 1][1]

        new_subseq_val = new_elem + best_pred_subseq_val

        list_len = len(best_subseq)
        num_deleted = 0

        while (num_deleted + insert_loc < list_len
               and best_subseq[insert_loc][1] <= new_subseq_val):
            del best_subseq[insert_loc]
            num_deleted += 1

        best_subseq.insert(insert_loc, (new_elem, new_subseq_val))

    return max(val for key, val in best_subseq)

tests = [eval(line) for line in """[]
[3]
[3, 2, 1]
[3, 2, 5, 6]
[9, 3, 2, 1, 4]
[3, 4, 1, 4, 1]
[9, 1, 2, 3, 4]
[1, 2, 4, 3, 4]
[9, 1, 2, 3, 4, 5, 10]
[3, 2, 1, 2, 3]""".split('\n')]

for test in tests:
    print(test, heaviest_subseq(test))

Анализ времени выполнения:

Каждый элемент имеет свою позицию вставки, которая ищется один раз, вставляется один раз и, возможно, удаляется один раз, в дополнение к постоянному количеству поисков значений в цикле. Поскольку я использую встроенный пакет bisect и пакет blist , каждая из этих операций O(log n). Таким образом, общее время выполнения O(n log n).

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

isaacg
источник
Интересно, очень отличное решение от моего .
orlp
2

Python, O (n log n)

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

def setmax(a, i, v):
    while i < len(a):
        a[i] = max(a[i], v)
        i |= i + 1

def getmax(a, i):
    r = 0
    while i > 0:
        r = max(r, a[i-1])
        i &= i - 1
    return r

def his(l):
    maxbit = [0] * len(l)
    rank = [0] * len(l)
    for i, j in enumerate(sorted(range(len(l)), key=lambda i: l[i])):
        rank[j] = i

    for i, x in enumerate(l):
        r = rank[i]
        s = getmax(maxbit, r)
        setmax(maxbit, r, x + s)

    return getmax(maxbit, len(l))

Двоичное индексированное дерево может выполнять две операции в log (n): увеличивать значение по индексу i и получать максимальное значение в [0, i). Мы инициализируем каждое значение в дереве равным 0. Мы индексируем дерево, используя ранг элементов, а не их индекс. Это означает, что если мы индексируем дерево по индексу i, все элементы [0, i) будут элементами меньше, чем элемент с рангом i. Это означает, что мы получаем максимум из [0, i), добавляем к нему текущее значение и обновляем его в i. Единственная проблема заключается в том, что это будет включать значения, которые меньше текущего значения, но идут позже в последовательности. Но поскольку мы перемещаемся по последовательности слева направо и инициализируем все значения в дереве на 0, они будут иметь значение 0 и, следовательно, не будут влиять на максимум.

orlp
источник
1

Python 2 - O(n^2)- 114 байт

def h(l):
 w=0;e=[]
 for i in l:
    s=0
    for j,b in e:
     if i>j:s=max(s,b)
    e.append((i,s+i));w=max(w,s+i)
 return w
Tyilo
источник
1

C ++ - O(n log n)- 261 байт

Должно быть исправлено сейчас:

#include <set>
#include <vector>
int h(std::vector<int>l){int W=0,y;std::set<std::pair<int,int>>S{{-1,0}};for(w:l){auto a=S.lower_bound({w,-1}),b=a;y=prev(a)->second+w;for(;b!=S.end()&&b->second<=y;b++){}a!=b?S.erase(a,b):a;W=y>W?y:W;S.insert({w,y});}return W;}
Tyilo
источник
auto S=set<pair<I,I>>();длиннее, чем просто set<pair<I,I>> S;. #define I intдлиннее чем using I=int;. Нет необходимости присваивать nчто-либо, вы можете заменить auto n=*prev(S.lower_bound({w,-1}));I y=n.secondна I y=prev(S.lower_bound({w,-1}))->second+w;.
Orlp
Да, и инициализация Sочень запутанная, вы можете просто отказаться от вставки и использования std::set<std::pair<int,int>>S{{-1,0}};.
Orlp
@ или спасибо! Это показывает, что я не использую c ++;)
Tyilo
Вот гораздо более короткая версия (все еще требуется набор и векторное включение):using namespace std;using I=int;I h(vector<I>l){I W=0;set<pair<I,I>>S{{-1,0}};for(I w:l){I y=prev(S.lower_bound({w,-1}))->second+w;W=max(W,y);S.insert({w,y});}return W;}
orlp
Ох и дамп std::max, используйте W=y>W?y:W;.
Orlp
0

Matlab, O ( n 2 n ), 90 байт

function m=f(x)
m=0;for k=dec2bin(1:2^numel(x)-1)'==49
m=max(m,all(diff(x(k))>0)*x*k);end

Примеры:

>> f([])
ans =
     0
>> f([3])
ans =
     3
>> f([3, 2, 5, 6])
ans =
    14
Луис Мендо
источник
0

Python, O (2 n ), 91 байт

Это больше для развлечения, чем для соревнования. Тайное рекурсивное решение:

h=lambda l,m=0:l and(h(l[1:],m)if l[0]<=m else max(h(l[1:],m),l[0]+h(l[1:],l[0])))or 0
orlp
источник
1
max(m,l[0])учитывая, что not(l[0]<m)это просто l[0], конечно?
Питер Тейлор
@PeterTaylor Derp.
Orlp
Этот ответ не выглядит серьезным соперником.
pppery