Maximum Sum Increasing Subsequence in $$$O(n \log n)$$$?

Revision en1, by Qualified, 2021-01-04 02:18:57

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/.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Qualified 2021-01-04 02:18:57 438 Initial revision (published)