All subscripts with the highest grouping score

Their thinking

So we know that we need to go through the array at least once, and figure out the number of left 0 elements and right 1 elements as we go through. How to find the number of 0 and 1 in the left and right array?

Violence is

class Solution {
public:
    vector<int> maxScoreIndices(vector<int>& nums) {
        vector<int> ans;
        int n = nums.size(a);int sumleft = 0, sumright = 0, sum = 0, max = sum;
        for (int i = 0; i <= n; i++) 
        {
            sumleft = 0, sumright = 0;
            for(int j = 0; j < i; j++)
            {
                if(nums[j] == 0) sumleft ++;
            }
            for(int k = i; k < n; k++)
            {
                if(nums[k] == 1) sumright ++;              
            }
            sum = sumleft + sumright;   
            
            if (sum > max) 
            {
                max = sum;
                ans.clear(a); ans.push_back(i);
            }
            else if (sum == max) ans.push_back(i);
        }
        
        returnans; }};Copy the code

J and k traversed the array at the same time as I traversed the array, so the time complexity reached O(n^2).

I can’t go around this time, so we have to reduce the time complexity by finding the number of elements in the array. In this case, we can use prefix and array to implement the process, it is only O(1) time to evaluate the value of the array prefix sum, which meets our requirements nicely. But it is clear that the subject is not simply the prefix and just a matter of, it needs to know the number of 1 s and 0 s, for 1, we can as a simple prefix and to calculate good, after all the prefix and the values in the array naturally represents the number of 1 from beginning to end, then to 0, actually also only need to use value of the current I (the number of elements in the array on the left) minus in the array on the left The number of ones will do.

After we’ve done that, we haven’t quite met the problem. They’re not simply asking us to give us the highest score, they’re asking us to give us all the different indices for the highest score. We can easily do this by using a vector ans: define a Max value and continually compare it to the sum of each iteration of I: if sum == Max, we push the current value of I into ans; If sum > Max, empty the ans array and insert the current value of I into the ans array. Remember Max = sum. The final code is as follows:

The final code

class Solution {
public:
    vector<int> maxScoreIndices(vector<int>& nums) {
        int s[100010];
        vector<int> ans;
        int n = nums.size(a); s[0] = nums[0];
        for (int i = 1; i < n; i ++ ) s[i] = s[i - 1] + nums[i];// Build prefixes and arrays
        
        int sumleft = 0, sumright = 0, sum = 0, max = sum;
        for (int i = 0; i <= n; i++) 
        {
            if(i == 0) ans = s[n - 1];
            else
            {
                sumleft = i - s[i - 1];
                sumright = s[n - 1] - s[i - 1];
                sum = sumleft + sumright;   
            }// Calculate the score for each I difference

            if (sum > max) 
            {
                max = sum;
                ans.clear(a); ans.push_back(i);
            }
            else if (sum == max) ans.push_back(i);// Maintain the answer array ans
        }

        returnans; }};Copy the code

Time complexity

Since the time complexity of the prefix and array is O(1), the time complexity of the final code is O(n), which meets the requirements of the problem.