title: Longest `subsequence` of balanced parentheses
body: <p>I am trying to solve a variant of a <a href="https://stackoverflow.com/questions/26601647/length-of-longest-chain-of-balanced-parentheses-in-given-ranges/26603226#26603226">problem</a> I asked earlier:</p>
  
  <blockquote>
    <p>Given a string of parentheses (length &lt;= 1,000,000) and a list of
    range queries, find the longest <strong>subsequence</strong> of balanced
    parentheses within each of the ranges for each of the &lt;= 100,000
    queries</p>
  </blockquote>
  
  <p>I found this <a href="https://stackoverflow.com/questions/13074163/longest-subsequence-of-s-that-is-balanced">other</a> SO question that is similar but only has an O(N^3) algorithm.</p>
  
  <p>I believe that a DP solution of the form <code>dp[i, j] = longest balanced subsequence in [i .. j]</code> should work because once computed, this would enable to to answer all of the range queries just by querying the DP table. However, even an O(N^2) solution to this problem would exceed the time limits due to the large possible input string length.</p>
  
  <p>Further, the trick of using a stack to keep track of matching parentheses no longer directly works because you are looking for subsequences, not substrings.</p>
  
  <p>I have a method which I think might work but am not sure of:</p>
  
  <p>The length of the longest subsequence of balanced parentheses within an interval is the sum of the lengths of the longest non-overlapping substrings of balanced parentheses within that interval.</p>
  
  <p>For example, if you have the string </p>
  
  <blockquote>
    <p><code>0 1 2 3 4 5 6 7 8 9 10 11 12 13 14</code></p>
    
    <p><code>) ) ( ( ) ( ( ) ) )  )  (  (  )  )</code></p>
  </blockquote>
  
  <p>The length of the longest subsequence of balanced parentheses in the interval [0, 8] (inclusive) is 5. This length is equal to that of the sum of the lengths of the longest non-overlapping substrings within the interval: "( )" + "( ( ) )".</p>
  
  <p>Will this method always hold, or is there a better way?</p>