# 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
```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
```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
```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)

 */
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/prefix-sum/2155.-all-divisions-with-the-highest-score-of-a-binary-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.