Qualified's blog

By Qualified, history, 4 years ago, In English

I am asking this question for another person btw.

I know how to find LIS in $$$O(n \log n)$$$ with binary search and is pretty well known. I am trying to find the Maximum Sum Increasing Subsequence in $$$O(n \log n)$$$. This can be solved using a BIT or a segtree, but is there an approach with binary search like LIS? https://www.geeksforgeeks.org/maximum-sum-increasing-subsequence-dp-14/.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You could do it via a set in a very similar way. The binary search approach works mostly in a redundancy-elimination fashion. You could store the set of "non-redundant" pairs (lastElement, Sum). A pair (x, y) is redundant if there is a pair (z, t) with z <= x and t > y (smaller last element, bigger sum). If you maintain the no-redundant pairs invariant, you'll have a list of pairs that, when sorted by first field, give increasing values in the other field. Once you've figured what pair needs to be inserted (if any at all) after having processed the current number, you also need to clean stuff up: that is, look for pairs that following the insertion of this new one have become redundant. This might appear as potentially linear per element, and it indeed may be, only that it amortizes overall: as you insert at most one pair at once, you can't, overall, delete more than N pairs. The main difference between this and the normal case is that here you can have further redundancies after inserting a pair (in the binary search case the one thing that you replace is precisely what would be redundant if looked upon as a set of pairs of lengths and values) and that neither of the dimensions allows for a nice indexing (as opposed to before when the length was bounded by N)