#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

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