解题思路

这道题有2种解法。

算法1 (双指针)

1. 定一个分界点k，k这个分界点从1开始枚举
2. 对于数字0，从s[0]开始枚举，枚举范围是0~k，左边如果是0，对应的res就++。
3. 对于数字1，从s[k]开始枚举，枚举范围是k~n，右边如果是1，对应的res就++。
4. 最后ans取最大值即可。
5. 算法核心是枚举分界点k，针对于k的左边，只在乎0的个数；针对于k的右边，只在乎1的个数。

代码

class Solution {
public:
    int maxScore(string s) {
        int n = s.size();
        int res = 0, ans = 0;

        for(int k = 1; k < n; k ++)
        {
            res = 0;
            for(int i = 0; i < k; i ++)
                if(s[i] == '0') res ++;

            for(int j = k; j < n; j ++)
                if(s[j] == '1') res ++;

            ans = max(ans, res);
        }

        return ans;
    }
};

算法2 (线性扫描)

1. 先计算s[0]是否是0的个数，如果是0，sum ++
2. 然后计算该字符串中所有1的个数
3. 接下来，res为维护所有情况的最大值，tmp表示当前分界点，也就是左边的0和右边的1的个数和。
   tmp就是分隔左右两边的中间点，tmp压在左边(计算0的个数)的闭区间那里。
4. 当枚举到1，就是一个新的1进入到了左边，也就是右边少了一个1。
5. 所以如果碰到了0，对应的tmp ++；碰到了1，对应地tmp --。i.e. 当右移的时候遇到一个0的时候，相当于左边多了一个0，但是右边的1没有少，所以对应的tmp ++。

代码

class Solution {
public:
    int maxScore(string s) {
        int sum = 0;
        if(s[0] == '0') sum ++;

        for(int i = 1; i < s.size(); i ++)
            if(s[i] == '1') sum ++;

        int res= sum;
        int tmp = sum;
        for(int i = 1; i < s.size() - 1; i ++)
        {
            if(s[i] == '0') tmp ++;
            else tmp --;

            res = max(res, tmp);
        }

        return res;
    }
};