Problem statement

https://leetcode.com/problems/maximum-score-after-splitting-a-string/

Solution

Use cumulative sums to fast evaluate score.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def maxScore(self, s):
        n, ans = len(s), 0
        acc = [0] + list(accumulate([int(i) for i in s]))
        for i in range(1, n):
            ans = max(ans, i - 2*acc[i] + acc[-1])
        return ans