December 29, 2021: the elimination rules of a subsequence are as follows: 1. In a subsequence

2021-12-29： The elimination rule of a subsequence is as follows :

1、 In a subsequence , If '1' On the left '0', So these two characters ->"01" Can eliminate ;

2、 In a subsequence , If '3' On the left '2', So these two characters ->"23" Can eliminate ;

3、 When a part of this subsequence is eliminated , Think that other characters will automatically stick together , You can continue to look for opportunities to eliminate .

such as , Some subsequence "0231", First eliminate "23", Then the rest of the characters are pasted together and become "01", If you continue to erase, there will be no characters ,

If a subsequence passes the best way , Can be eliminated , So this subsequence is called “ Total elimination subsequence ”,

One consists only of '0'、'1'、'2'、'3' A string of four characters str, Many subsequences can be generated , return “ Total elimination subsequence ” Maximum length of ,

character string str length <= 200.

Real written test , Forget which company , But it's absolutely big .

answer 2021-12-29：

recursive .

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    str1 := "010101"
    fmt.Println(maxDisappear(str1))
    str2 := "021331"
    fmt.Println(maxDisappear(str2))
}

// str[L...R] On , Subsequences that can be eliminated , What's the longest ？
func f(str string, L, R int) int {
    if L >= R {
        return 0
    }
    if L == R-1 {
        if (str[L] == '0' && str[R] == '1') || (str[L] == '2' && str[R] == '3') {
            return 2
        } else {
            return 0
        }
        //return (str[L] == '0' && str[R] == '1') || (str[L] == '2' && str[R] == '3') ? 2 : 0;
    }
    // L...R  There are several characters  > 2
    // str[L...R] On , Subsequences that can be eliminated , What's the longest ？
    //  possibility 1, Subsequences that can be eliminated are not considered at all str[L], What's the longest ？
    p1 := f(str, L+1, R)
    if str[L] == '1' || str[L] == '3' {
        return p1
    }
    // str[L] =='0'  perhaps  '2'
    // '0'  Look for  '1'
    // '2'  Look for  '3'
    find := byte('1')
    if str[L] != '0' {
        find = '3'
    }
    //find := str[L] == '0' ? '1' : '3';
    p2 := 0
    // L() ......
    for i := L + 1; i <= R; i++ {
        // L(0) ..... i(1) i+1....R
        if str[i] == find {
            p2 = getMax(p2, f(str, L+1, i-1)+2+f(str, i+1, R))
        }
    }
    return getMax(p1, p2)
}

func maxDisappear(str string) int {
    if len(str) == 0 {
        return 0
    }
    return disappear(str, 0, len(str)-1)
}

// s[l..r] In terms of scope , As the title says , The length of the longest subsequence that can be eliminated 
func disappear(s string, l, r int) int {
    if l >= r {
        return 0
    }
    if l == r-1 {
        if (s[l] == '0' && s[r] == '1') || (s[l] == '2' && s[r] == '3') {
            return 2
        } else {
            return 0
        }
        //return (s[l] == '0' && s[r] == '1') || (s[l] == '2' && s[r] == '3') ? 2 : 0;
    }
    p1 := disappear(s, l+1, r)
    if s[l] == '1' || s[l] == '3' {
        return p1
    }
    p2 := 0
    find := byte('1')
    if s[l] != '0' {
        find = '3'
    }
    //find := s[l] == '0' ? '1' : '3';
    for i := l + 1; i <= r; i++ {
        if s[i] == find {
            p2 = getMax(p2, disappear(s, l+1, i-1)+2+disappear(s, i+1, r))
        }
    }
    return getMax(p1, p2)
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code