Consider the following classic elementary problem:Given a string of parens like ')((()()(()', find a maximum-length balanced subsequence: ')((()()(()' = '(()())'.Dynamic programming and only a bit of thinking yield a linear time solution.  (Try it, it's easy!)  I got interested in a generalization:Given a string of parens and associated costs, find a balanced subsequence with maximum total cost.Or formulated differently, minimize the total cost of unmatched items.As for my question: what's the fastest known solution?  Is there any literature on this fairly elementary problem?  I tried to look, but couldn't find the right keywords.Note that computing any order statistic of an unordered list (like eg finding the median) can be reduced to this problem with a very simple transformation.  That means that any solution for the maximum-cost balanced subsequence will have to be at least as complicated as the simplest median-finding schemes.  (This is mostly a hint that nature gives us that, if we are trying to find a deterministic linear time solution, it's gotta be at least as complicated as the median-of-medians algorithm.)
Maximum-cost balanced subsequence
randomized algorithms;matching