1422. 分割字符串的最大得分.md

1422. 分割字符串的最大得分

题目传送门

点击这里

解题思路

这道题如果用暴力的解法是可以的，时间复杂度是$ O(n^2)$，不过也可以进行优化，方法是统计第一次的得分情况，然后向后一次遍历，将每个点都当作切割点，如果切割点为0，则分数加一，否则减一。

代码

func maxScore(s string) int {
    score := int('1'-s[0]) + strings.Count(s[1:], "1")
    ans := score
    for _, c := range s[1 : len(s)-1] {
        if c == '0' {
            score++
        } else {
            score--
        }
        ans = max(ans, score)
    }
    return ans
}

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