Heaviest increasing subsequence 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:

                    [] -&gt;  0 ([])
                   [3] -&gt;  3 ([3])
             [3, 2, 1] -&gt;  3 ([3])
          [3, 2, 5, 6] -&gt; 14 ([3, 5, 6])
       [9, 3, 2, 1, 4] -&gt;  9 ([9])
       [3, 4, 1, 4, 1] -&gt;  7 ([3, 4])
       [9, 1, 2, 3, 4] -&gt; 10 ([1, 2, 3, 4])
       [1, 2, 4, 3, 4] -&gt; 10 ([1, 2, 3, 4])
[9, 1, 2, 3, 4, 5, 10] -&gt; 25 ([1, 2, 3, 4, 5, 10])
       [3, 2, 1, 2, 3] -&gt;  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.
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 &lt; list_len
               and best_subseq[insert_loc][1] &lt;= 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.