How to find increasing subsequence of numbers with maximum sum?

Question

How to find increasing subsequence of numbers with maximum sum. I find O(N^2) but I want to know O(N log N).

Thanks!

Answer 1

I'm assuming:

• You don't care about subsequence length at all.
• Subsequences don't need to be contiguous

This makes a world of difference!

---

Solution

Let an optimal set S of increasing subsequences (IS) for an array A be a set of ISs such that each IS s in A we have exactly one of:

• s in in S
• There is an IS s' in S such that
  • sum(s') >= sum(s) and
  • largest_element(s') <= largest_element(s)

The optimal set S can be ordered both by the largest element of the subsequences and their sum - the order should be the same. This is what I mean by smallest/largest sequence later.

Our algorithm must then find the optimal set of A and return its largest sequence. S can be calculated by:

S := {[]} //Contains the empty subsequence
for each element x in A:
   s_less := (largest sequence in S that ends in less than x)
   s := Append x to s_less
   s_more := (smallest sequence in S that has sum greater than s)

   Remove all subsequences in S that are between s_less and s_more 
    (they are made obsolete by 's')

   Add s to S

The largest subsequence in S is the largest subsequence in the array.

Each step can be implemented in O(log n) is S is a balanced binary tree. The n steps give O(n*log n) total complexity.

Caveat: There could very likely be some +- 1 error(s) in my pseudo code - finding them is left as an exercize to the reader :)

---

I'll try to give a concrete example. Maybe it helps make the idea clearer. The subsequence most to the right is always the best one so far but the other ones are because in the future they could grow to be the heaviest sequence.

curr array | Optimal Subsequences
[]              []

//best this we can do with 8 is a simgleton sequence:
[8]             [] [8]

//The heaviest sequence we can make ending with 12 is [8,12] for a total of 20
//We still keep the [8] because a couble of 9s and 10s might make it 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] and [8,12] obsolete (remove those).
//It not only is heavier but the last number is smaller.
[8,12,11,9,10]  [] [8] [8,9] [8,9,10]

Answer 2

Scan the array. Maintain a splay tree mapping each element x to the maximum sum of a subsequence ending in x. This splay tree is sorted by x (not the index of x), and each node is decorated with the subtree maximum. Initially the tree contains only a sentinel Infinity => 0. To process a new value y, search the tree for the leftmost value z such that y <= z. Splay z to the root. The subtree max M of z's left child is the maximum sum of a subsequence that y can extend. Insert (y, M + y) into the tree. At the end, return the tree max.