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

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

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

Примеры:

                    [] ->  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])

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

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

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

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).

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

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 и, следовательно, не будут влиять на максимум.

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

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;}

Matlab, O ( n 2 ⁿ ), 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

Python, O (2 ⁿ ), 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