2155. All Divisions With the Highest Score of a Binary Array

prefix sum idea,

cal left (0 count)

cal right (1 count)

sum both -> and find max result

T: O(n)
S: O(n)

```java
class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        int n = nums.length;
        int left[] = new int[n+1];
        left[0] = 0;
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (nums[i-1] == 0) {
                count++;
            }
            left[i] = count;
        }

        int right[] = new int[n+1];
        right[n] = 0;
        count = 0;
        for (int i = n-1; i >= 0; i--) {
            if (nums[i] == 1) {
                count++;
            }
            right[i] = count;
        }
        // System.out.println(Arrays.toString(left));
        // System.out.println(Arrays.toString(right));

        List<Integer> result = new ArrayList<>();
        int[] sum = new int[n+1];
        int max = 0;
        for (int i = 0; i <= n; i++) {
            sum[i] = left[i] + right[i];
            if (sum[i] > max) {
                result = new ArrayList<>();
                result.add(i);
                max = sum[i];
            } else if (sum[i] == max) {
                result.add(i);
            }
        }
        //System.out.println(Arrays.toString(sum));
        return result;
    }
}

/**
3: 0  1: 1

left point
[0,1,2,2,3]

right point
[1,1,1,0,0]

add together(in the process, we can get max number) -> [1,2,3,2,3] -> scan again -> get max index

get total zero, one count

record one side's zero count 


T: O(n)
S: O(n)

 */
```

more prefix sum

```java
class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        int n = nums.length;
        int left[] = new int[n+1];
        left[0] = 0;
        for (int i = 1; i <= n; i++) {
            left[i] = left[i-1] + (nums[i-1] == 0 ? 1 : 0);
        }

        int right[] = new int[n+1];
        right[n] = 0;
        for (int i = n-1; i >= 0; i--) {
            right[i] = right[i+1] + (nums[i] == 1 ? 1 : 0);
        }

        List<Integer> result = new ArrayList<>();
        int[] sum = new int[n+1];
        int max = 0;
        for (int i = 0; i <= n; i++) {
            sum[i] = left[i] + right[i];
            if (sum[i] > max) {
                result = new ArrayList<>();
                result.add(i);
                max = sum[i];
            } else if (sum[i] == max) {
                result.add(i);
            }
        }
        return result;
    }
}

/**
3: 0  1: 1

left point
[0,1,2,2,3]

right point
[1,1,1,0,0]

add together(in the process, we can get max number) -> [1,2,3,2,3] -> scan again -> get max index

get total zero, one count

record one side's zero count 


T: O(n)
S: O(n)

 */
```

Running count

T: O(n)

S: O(1)

```java
class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        int oneCount = 0;
        for (int num : nums) {
            oneCount++;
        }
        List<Integer> result = new ArrayList<>();
        result.add(0); // for like [1,1] max is in the beginning, no update result, so add 0 first
        int runningCount = oneCount;
        int max = oneCount;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                runningCount++;
            } else {
                runningCount--;
            }

            if (runningCount >= max) { // if [1,1] won't add any result here
                if (runningCount != max) {
                    result.clear();
                    max = runningCount;
                }
                result.add(i+1);
            }
        }
        return result;
    }
}
/**
running count

count all one count first
then if pass zero, runningCount will increase
vice versa

T: O(n)
S: O(1)

 */
```