# 1422. Maximum Score After Splitting a String

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

我只想的到這個QQ

## 暴力(n^2)

var maxScore = function (s) {
    let max = 0
    for (let i = 0; i < s.length-1; i++) {
        let temp = 0
        for (let j = 0; j <= i; j++) {
            if (s[j] === "0") temp++
        }
        for (let k = i + 1; k < s.length; k++) {
            if (s[k] === "1") temp++
        }
        max = Math.max(max, temp)
    }
    return max
};

## One pass O(n)

分數 = 左0 + 右1
右1 = 全1 - 左1
分數 = 左0 + 全1 - 左1

找到 左0 - 左1 最大值，另外處理最後一個數，因為算法左右切分沒有考慮到

var maxScore = function (s) {
    let ones = 0;
    let zeros = 0;
    let best = Number.MIN_SAFE_INTEGER; 

    for (let i = 0; i < s.length - 1; i++) {
        if (s.charAt(i) === '1') {
            ones++;
        } else {
            zeros++;
        }

        best = Math.max(best, zeros - ones);
    }

    if (s.charAt(s.length - 1) === '1') {
        ones++;
    }

    return best + ones;
};