Local search in CFG algorithm

Question

Is there an algorithm that can solve the following problem in polynomial time:

We connect the bits in bitrate:

• 0 can only be connected to 1
• each bit can only be connected once
• connections cannot intersect

What is the maximum number of connections for a given bit set?

Answer 1

Here we can use dynamic programming.

• The state (l, r)is a [l, r]substring of the given string.

• The status value is the maximum number of matching characters in the substring.

• The main case is trivial: for all substrings shorter than 2, the answer is 0.

• For all the longer substrings, we can do two things:

  • .

  • - ( , ).

. O(n^3) ( O(n^2) O(n) ). (memoization ):

def calc(l, r)
    if l >= r
        return 0
    res = calc(l + 1, r)
    for k = l + 1 to r
        if match(s[l], s[k]) // match checks that two characters match
            res = max(res, 1 + calc(l + 1, k - 1) + calc(k + 1, r)) 
    return res 

Answer 2

, 0s 1s - 0s 1s .

, , . O (n).