2021-12-25: given a string s consisting only of 0 and 1, assume that the subscript is from

2021-12-25： Given a given one, only 0 and 1 Composed string S, Suppose the subscript is from 1 Start , Regulations i Character value of position Vi The calculation method is as follows :

1 i == 1 when ,Vi = 1;

2 i > 1 when , If Si != Si-1,Vi = 1;

3 i > 1 when , If Si == Si-1,Vi = Vi-1 + 1.

You can delete it at will S The characters in , Back to the whole S Maximum value of ,

String length <=5000.

From Tencent .

answer 2021-12-25：

recursive . Try the model from left to right .

At present index The character of the position is reserved ; At present index The character of position is not reserved . The maximum of these two cases .

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

package main

import "fmt"

func main() {
    ret := max1("000001100000")
    fmt.Println(ret)
}

func max1(s string) int {
    if len(s) == 0 {
        return 0
    }
    str := []byte(s)
    arr := make([]int, len(str))
    for i := 0; i < len(arr); i++ {
        if str[i] == '0' {

        } else {
            arr[i] = 1
        }
    }
    return process1(arr, 0, 0, 0)
}

//  Recursive meaning  :
//  Currently in arr[index...] Make a choice on , str[index...] Left side , The latest figure is lastNum
//  also lastNum Value brought , Has been pulled up to baseValue
//  Back in the str[index...] Make a choice on , The ultimate maximum value 
// index -> 0 ~ 4999
// lastNum -> 0 or 1
// baseValue -> 1 ~ 5000
// 5000 * 2 * 5000 -> 5 * 10^7( too !)
func process1(arr []int, index, lastNum, baseValue int) int {
    if index == len(arr) {
        return 0
    }
    curValue := 0
    if lastNum == arr[index] {
        curValue = baseValue + 1
    } else {
        curValue = 1
    }

    //  At present index The character of the position is reserved 
    next1 := process1(arr, index+1, arr[index], curValue)
    //  At present index The character of position is not reserved 
    next2 := process1(arr, index+1, lastNum, baseValue)
    return getMax(curValue+next1, next2)
}

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

The results are as follows ：

picture

---

Zuo Shen java Code