algorithm - How to find increasing subsequence of numbers with maximum sum? -

how find increasing subsequence of numbers maximum sum. find o(n^2) want know o(n log n).

thanks!

i'm assuming:

• you don't care subsequence length @ all.
• subsequences don't need contiguous

this makes world of difference!

---

solution

let optimal set s of increasing subsequences (is) array a set of iss such each s in a have 1 of:

• s in in s
• there s' in s such
  • sum(s') >= sum(s) and
  • largest_element(s') <= largest_element(s)

the optimal set s can ordered both largest element of subsequences , sum - order should same. mean smallest/largest sequence later.

our algorithm must find optimal set of a , return largest sequence. s can calculated by:

s := {[]} //contains empty subsequence each element x in a:    s_less := (largest sequence in s ends in less x)    s := append x s_less    s_more := (smallest sequence in s has sum greater s)     remove subsequences in s between s_less , s_more      (they made obsolete 's')     add s s 

the largest subsequence in s largest subsequence in array.

each step can implemented in o(log n) s balanced binary tree. n steps give o(n*log n) total complexity.

caveat: there +- 1 error(s) in pseudo code - finding them left exercize reader :)

---

i'll try give concrete example. maybe helps make idea clearer. subsequence right best 1 far other ones because in future grow heaviest sequence.

curr array | optimal subsequences []              []  //best can 8 simgleton sequence: [8]             [] [8]  //the heaviest sequence can make ending 12 [8,12] total of 20 //we still keep [8] because couble of 9s , 10s might make better tahn 8+12 [8,12]          [] [8] [8,12]  [8,12,11]       [] [8] [8,11] [8,12] [8,12,11,9]     [] [8] [8,9] [8,11] [8,12]  //[8,9,10] makes [8,11] , [8,12] obsolete (remove those). //it not heavier last number smaller. [8,12,11,9,10]  [] [8] [8,9] [8,9,10]