Heaviest increasing subsequence

Question

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A strictly increasing subsequence is a subsequence in which every element is bigger than the preceding one.

The heaviest increasing subsequence of a sequence is the strictly increasing subsequence that has the biggest element sum.

Implement a program or function in your language of choice that finds the element sum of the heaviest increasing subsequence of a given list of non-negative integers.

Examples:

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

Note that you only have to give the element sum of the heaviest increasing subsequence, not the subsequence itself.

---

The asymptotically fastest code wins, with smaller code size in bytes as a tiebreaker.

Answer 1

javascript (ES6) O(n log n) 253 characters

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}

this uses fenwick trees (a maximum fenwick tree) to find maxima of certain subsequences.

basically, in the underlying array of the datatype, each place is matched with an element from the input list, in the same order. the fenwick tree is initialized with 0 everywhere.

from the smallest to the biggest, we take an element from the input list, and look for the maximum of the elements to the left. they are the elements that may be before this one in the subsequence, because they are to the left in the input sequence, and are smaller, because they entered the tree earlier.

so the maximum we found is the heaviest sequence that can get to this element, and so we add to this the weight of this element, and set it in the tree.

then, we simply return the maximum of the whole tree is the result.

tested on firefox

Answer 2

Python, O(n log n)

I didn't golf this, because I'm competing primarily on the fastest code side of things. My solution is the heaviest_subseq function, and a test harness is also included at the bottom.

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

Runtime analysis:

Each element has its insertion position looked up once, is inserted once, and is possibly deleted once, in addition to a constant number of value lookups per loop. Since I am using the built-in bisect package and the blist package, each of those operations are O(log n). Thus, the overall runtime is O(n log n).

The program works by maintaining a sorted list of best possible increasing subsequences, represented as a tuple of ending value and sequence sum. An increasing subsequence is in that list if there are no other subsequences found so far whose ending value is smaller and sum is at least as large. These are maintained in increasing order of ending value, and necessarily also in increasing order of sum. This property is maintained by checking the successor of each newly found subsequence, and deleting it if its sum is not large enough, and repeating until a subsequence with a larger sum is reached, or the end of the list is reached.

Answer 3

Python, O(n log n)

I used an index transform and a nifty data structure (binary indexed tree) to trivialize the problem.

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

The binary indexed tree can do two operations in log(n): increase a value at index i and get the maximum value in [0, i). We initialize every value in the tree to 0. We index the tree using the rank of elements, not their index. This means that if we index the tree at index i, all elements [0, i) are the elements smaller than the one with rank i. This means that we get the maximum from [0, i), add the current value to it, and update it at i. The only issue is that this will include values which are less than the current value, but come later in the sequence. But since we move through the sequence from left-to-right and we initialized all values in the tree to 0, those will have a value of 0 and thus not affect the maximum.

Answer 4

Python 2 - O(n^2) - 114 bytes

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

Answer 5

C++ - O(n log n) - 261 bytes

Should be fixed now:

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

Answer 6

Python, O(2ⁿ), 91 bytes

This is more for fun than to be competitive. An arcane recursive solution:

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

Answer 7

Matlab, O(n 2ⁿ), 90 bytes

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

Examples:

>> f([])
ans =
     0
>> f([3])
ans =
     3
>> f([3, 2, 5, 6])
ans =
    14