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.

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.

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

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

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

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

Rust ,\$\mathcal{O}(n \log n)\$

Port of @isaacg's answer

run it on Rust Playground!

use std::cmp::Ordering;

fn heaviest_subseq(in_list: &[i32]) -> i32 {
    let mut best_subseq = vec![(0, 0)];

    for new_elem in in_list {
        let insert_loc = match best_subseq
            .binary_search_by(|&(key, _)| if key < *new_elem { Ordering::Less } else { Ordering::Greater })
        {
            Ok(index) => index,
            Err(index) => index,
        };

        let best_pred_subseq_val = best_subseq[insert_loc - 1].1;

        let new_subseq_val = new_elem + best_pred_subseq_val;

        let mut num_deleted = 0;

        while num_deleted + insert_loc < best_subseq.len() && best_subseq[insert_loc].1 <= new_subseq_val {
            best_subseq.remove(insert_loc);
            num_deleted += 1;
        }

        best_subseq.insert(insert_loc, (*new_elem, new_subseq_val));
    }

    best_subseq.into_iter().map(|(_, val)| val).max().unwrap()
}

fn main() {
    let tests = [
        &[][..],
        &[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][..],
    ];

    for test in &tests {
        println!("{:?} {:?}", test, heaviest_subseq(test));
    }
}