最重增长子序列

Question

子序列是可以通过删除某些元素而不改变其余元素的顺序从另一个序列派生的序列。严格增长子序列是指每个元素都大于前一个元素的子序列。

序列最大的增长子序列是元素和最大的严格增长子序列。

用您所选择的语言实现一个程序或函数，该程序或函数查找给定的非负整数列表中最重的递增子序列的元素和。

示例：

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

请注意，您只需给出最重增长子序列的元素和，而不是子序列本身。

渐进最快的代码获胜，以字节为单位的较小的代码大小作为平局者。

Answer 1

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上测试

Answer 2

Python，O(n log )

我没有这么做，因为我主要是在最快速的代码方面竞争。我的解决方案是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))

运行时分析：

每个元素的插入位置只查找一次，插入一次，并可能删除一次，而且每个循环的值查找都是固定的。由于我使用的是内置的除法包和blist包，这些操作中的每一个都是O(log n)。因此，总体运行时是O(n log n)。

该程序的工作方式是维护一个排序列表，列出可能增加的最佳子序列，表示为结束值和序列和的元组。如果到目前为止还没有发现其他子序列，其结束值较小且和至少相同大，则在该列表中将出现一个递增子序列。这些都是按期末价值递增的顺序维持的，也必然是按总和的增加顺序维持的。通过检查每个新发现的子序列的后继序列，如果其和不够大，则删除该属性，并重复该属性，直到达到较大和的子序列或到达列表的末尾为止。

Answer 3

Python，O(n log )

我使用了一个索引转换和一个漂亮的数据结构(二进制索引树)来解决这个问题。

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，因此不会影响最大值。