[数据结构与算法]2021-12-25：给定一个只由0和1组成的字符串S，假设下标从1开始，规定i位置的字符价值V[i]计算方式如下

2021-12-25：给定一个只由0和1组成的字符串S，假设下标从1开始，规定i位置的字符价值V[i]计算方式如下 :
1 i == 1时，V[i] = 1；
2 i > 1时，如果S[i] != S[i-1]，V[i] = 1；
3 i > 1时，如果S[i] == S[i-1]，V[i] = V[i-1] + 1。
你可以随意删除S中的字符，返回整个S的最大价值，
字符串长度<=5000。
来自腾讯。

答案2021-12-25：

递归。从左往右的尝试模型。
当前index位置的字符保留；当前index位置的字符不保留。这两种情况取最大值。

代码用golang编写。代码如下：

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)
}

// 递归含义 :
// 目前在arr[index...]上做选择, str[index...]的左边，最近的数字是lastNum
// 并且lastNum所带的价值，已经拉高到baseValue
// 返回在str[index...]上做选择，最终获得的最大价值
// index -> 0 ~ 4999
// lastNum -> 0 or 1
// baseValue -> 1 ~ 5000
// 5000 * 2 * 5000 -> 5 * 10^7(过!)
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
    }

    // 当前index位置的字符保留
    next1 := process1(arr, index+1, arr[index], curValue)
    // 当前index位置的字符不保留
    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
    }
}

执行结果如下：

左神java代码