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.

Answer 3

I encountered a similar question on codeforces. The problem can be done using segment trees with coordinate compression or using balanced binary search trees. Refer to the below links for detailed explaination.

maximum sum increasing sequence

After reading it, you can try this question on codeforces.

Answer 4

1.) Sort your subsequence

2.) iterate through your list, adding the next element to the previous element

3.) Once you reach two elements who's sums are greater than maximum_sum, stop. Everything previous can be combined together to be <= maximum_sum.

This assumes you are asking to add two elements to make maximum_sum. The general concept can be generalized for 0-N summations, where N is the length of your "numbers". However, you did not clarify what you were actually adding together, so I made an assumption. Also, I'm not sure if this will give you the "LONGEST" subsequence of numbers, but it will give you a subsequence of numbers in N log N.

This was an interview question Amazon.com asked me while I was puking my guts out from food poisoning on round one of interviews. I made it to round two of interviews, and they didn't seem to want to move forward past that point. Hopefully you do better than I did if this is an interview question, so my answer might not be the best, but hopefully it's better than saying you have a duplicate...

Hopefully this helps,

-Brian J. Stinar-