Эффективный в пространстве алгоритм поиска наибольшего сбалансированного подмассива?

Question

, учитывая массив из 0 и 1, найдите максимальный подмассив таким образом, чтобы число нулей и 1 было равным. Это необходимо сделать за время O (n) и пространство O (1).

У меня есть алгоритм, который делает это за время O (n) и пространство O (n). Он использует массив префиксных сумм и использует тот факт, что если число 0 и 1 одинаково, то sumOfSubarray = lengthOfSubarray / 2

#include<iostream>
#define M 15

using namespace std;

void getSum(int arr[],int prefixsum[],int size) {
    int i;
    prefixsum[0]=arr[0]=0;
    prefixsum[1]=arr[1];
    for (i=2;i<=size;i++) {
        prefixsum[i]=prefixsum[i-1]+arr[i];
    }
}

void find(int a[],int &start,int &end) {
    while(start < end) {
        int mid = (start +end )/2;
        if((end-start+1) == 2 * (a[end] - a[start-1]))
                break;
        if((end-start+1) > 2 * (a[end] - a[start-1])) {
            if(a[start]==0 && a[end]==1)
                    start++; else
                    end--;
        } else {
            if(a[start]==1 && a[end]==0)
                    start++; else
                    end--;
        }
    }
}

int main() {
    int size,arr[M],ps[M],start=1,end,width;
    ;
    cin>>size;
    arr[0]=0;
    end=size;
    for (int i=1;i<=size;i++)
            cin>>arr[i];
    getSum(arr,ps,size);
    find(ps,start,end);
    if(start!=end)
            cout<<(start-1)<<" "<<(end-1)<<endl; else cout<<"No soln\n";
    return 0;
}

Answer 1

Теперь мой алгоритм - O (n) время и O (Dn) пространство, где Dn - общее несоответствие в списке.

Это решение не изменяет список.

пусть D будет разницей 1 и 0, найденных в списке.

Сначала давайте линейно пройдемся по списку и вычислим D, просто чтобы посмотреть, как он работает:

Я собираюсь использовать этот список в качестве примера: l = 1100111100001110

Element   D
null      0
1         1
1         2   <-
0         1
0         0
1         1
1         2
1         3
1         4
0         3
0         2
0         1
0         0
1         1
1         2
1         3
0         2   <-

Нахождение самого длинного сбалансированного подмассива эквивалентно нахождению 2 равных элементов в D, которые являются более удаленной квартирой.(в этом примере 2 2 отмечены стрелками.)

Самый длинный сбалансированный подмассив находится между первым вхождением элемента +1 и последним вхождением элемента.(первая стрелка +1 и последняя стрелка: 00111100001110)

Примечание:

Самый длинный подмассив всегда будет между 2 элементами D, которые находятся между [0, Dn] где Dn - последний элемент D. (Dn = 2 в предыдущем примере) Dn - общий дисбаланс между 1 и 0 в списке.(или [Dn, 0], если Dn отрицателен)

В этом примере это означает, что мне не нужно «смотреть» на 3 с или 4 с

Доказательство:

Пусть Dn> 0.

Если существует подмассив, ограниченный P (P> Dn).Так как 0

P не может быть меньшечем 0 по тем же причинам

доказательство одинаково для Dn <0 </p>

Теперь давайте поработаем над D, D не случайно, разница между двумя последовательными элементами всегда1 или -1.Кроме того, существует легкая биекция между D и начальным списком.Поэтому у меня есть 2 решения этой проблемы:

• первое - отслеживать первое и последнее появление каждого элемента в D, которые находятся между 0 и Dn (см. Примечание).
• секунда - преобразовать список в D, а затем работать с D.

---

ПЕРВОЕ РЕШЕНИЕ

В настоящее время я не могу найтилучший подход, чем первый:

Сначала вычислите Dn (в O (n)).Dn = 2

Во-вторых, вместо создания D, создайте словарь, в котором ключами является значение D (между [0 и Dn]), а значением каждого ключа является пара (a, b), где aявляется первым вхождением ключа, а b последним.

Element   D DICTIONNARY
null      0 {0:(0,0)}
1         1 {0:(0,0) 1:(1,1)}
1         2 {0:(0,0) 1:(1,1) 2:(2,2)}
0         1 {0:(0,0) 1:(1,3) 2:(2,2)}
0         0 {0:(0,4) 1:(1,3) 2:(2,2)}
1         1 {0:(0,4) 1:(1,5) 2:(2,2)}
1         2 {0:(0,4) 1:(1,5) 2:(2,6)}
1         3 { 0:(0,4) 1:(1,5) 2:(2,6)}
1         4 {0:(0,4) 1:(1,5) 2:(2,6)}  
0         3{0:(0,4) 1:(1,5) 2:(2,6) }
0         2 {0:(0,4) 1:(1,5) 2:(2,9) }
0         1 {0:(0,4) 1:(1,10) 2:(2,9) } 
0         0 {0:(0,11) 1:(1,10) 2:(2,9) } 
1         1 {0:(0,11) 1:(1,12) 2:(2,9) } 
1         2 {0:(0,11) 1:(1,12) 2:(2,13)}
1         3 {0:(0,11) 1:(1,12) 2:(2,13)} 
0         2 {0:(0,11) 1:(1,12) 2:(2,15)} 

, и вы выбрали элемент с наибольшим отличием: 2: (2,15) и равен l [3:15] = 00111100001110 (сl = 1100111100001110).

Сложность времени:

2 прохода, первый для накопления Dn, второй для построения словаря.найти максимальное значение в словаре.

Итого: O (n)

Пространство сложности:

текущий элемент в D: O (1)словарь O (Dn)

Я не беру 3 и 4 в словаре из-за замечания

Сложность O (n) времени и O (Dn) пространства(в среднем случае Dn << n). </strong>

Я думаю, что для этого подхода может быть лучший способ, чем словарь.

Любое предложение приветствуется.

Надеюсь, что это поможет

---

ВТОРОЕ РЕШЕНИЕ (ПРОСТО ИДЕЯ, А НЕ РЕАЛЬНОЕ РЕШЕНИЕ)

Второй способ - преобразовать вашесписок в D. (так как легко вернуться из D в список, все в порядке).(O (n) время и O (1) пространство, так как я преобразую список на месте, даже если он не может быть «действительным» O (1))

Тогда из D вам нужно найти2 равных элемента, которые являются более удаленными.

похоже, что найти самый длинный цикл в связанном списке, модификация алгоритма Ричарда Брента может вернуть самый длинный цикл, но я не знаю, как это сделать, и потребовалось бы O (n) время и O (1) пространство.

Как только вы найдете самый длинный цикл, вернитесь к первому списку и распечатайте его.

Этот алгоритм потребует O (n) времени и O (1) космическая сложность.

Answer 2

Другой подход, но все равно O (n) время и память. Начните с предложения Нейла, рассматривайте 0 как -1.

Обозначения: A[0, …, N-1] - ваш массив размером N, f(0)=0, f(x)=A[x-1]+f(x-1) - функция

Если вы построите график f, вы увидите, что вы ищете точки, для которых f(m)=f(n), m=n-2k, где k-положительный натуральный. Точнее, только для x, такой, что A[x]!=A[x+1] (и последний элемент в массиве), вы должны проверить, встречалось ли уже f(x). К сожалению, теперь я не вижу улучшения по сравнению с массивом B[-N+1…N-1], где будет храниться такая информация.

Для завершения моей мысли: B[x]=-1 изначально, B[x]=p когда p = min k: f(k)=x. И алгоритм такой (перепроверьте, я очень устал):

fx = 0
B = new array[-N+1, …, N-1]
maxlen = 0
B[0]=0
for i=1…N-1 :
    fx = fx + A[i-1]
    if B[fx]==-1 :
        B[fx]=i
    else if ((i==N-1) or (A[i-1]!=A[i])) and (maxlen < i-B[fx]):
        We found that A[B[fx], …, i] is best than what we found so far
        maxlen = i-B[fx]

---

Редактировать : Две мысли о постели (= выяснил, лежа в постели: P):

1) Вы можете выполнить двоичный поиск результата по длине подмассива, что даст O (n log n) времени и O (1) алгоритма памяти. Давайте используем функцию g(x)=x - x mod 2 (потому что подмассивы, сумма которых равна 0, всегда имеют четную длину). Начнем с проверки, если весь массив равен 0. Если да, то мы закончили, в противном случае продолжаем. Теперь мы принимаем 0 в качестве начальной точки (мы знаем, что есть подмассив такой длины и «свойства суммирования до нуля») и g (N-1) в качестве конечной точки (мы знаем, что такого подмассива нет). Давайте сделаем

    a = 0
    b = g(N-1)
    while a<b : 
        c = g((a+b)/2)
        check if there is such subarray in O(n) time
        if yes:
            a = c
        if no:
            b = c
    return the result: a (length of maximum subarray)

Проверка подмассива с «свойством суммирования до нуля» некоторой заданной длины L проста:

    a = 0
    b = L
    fa = fb = 0
    for i=0…L-1:
        fb = fb + A[i]
    while (fa != fb) and (b<N) :
        fa = fa + A[a]
        fb = fb + A[b]
        a = a + 1
        b = b + 1
    if b==N:
        not found
    found, starts at a and stops at b

2) … вы можете изменить входной массив? Если да и если память O (1) точно означает, что вы используете без дополнительного пространства (кроме постоянного числа элементов) , то просто сохраните значения таблицы префиксов во входном массиве. Больше не используется места (кроме некоторых переменных): D

И снова, дважды проверьте мои алгоритмы, так как я очень устал и мог допускать отдельные ошибки.

Answer 3

Если ваш алгоритм действительно действителен во всех случаях (см. Мой комментарий к вашему вопросу, отмечая некоторые исправления к нему), обратите внимание, что массив префиксов является единственным препятствием для достижения вашей постоянной цели в памяти.

Изучение *Функция 1003 * показывает, что этот массив можно заменить двумя целыми числами, что исключает зависимость от длины ввода и решает вашу проблему.Обратите внимание на следующее:

• Вы зависите только от двух значений в массиве префиксов в функции find.Это a[start - 1] и a[end].Да, start и end меняются, но заслуживает ли это массив?
• Посмотрите на прогресс вашего цикла.В конце start увеличивается или end уменьшается только на один .
• С учетом предыдущего оператора, если вы должны заменить значение a[start - 1] на целое числоКак бы вы обновили его значение?Другими словами, для каждого перехода в цикле, который изменяет значение start, что вы можете сделать, чтобы соответствующим образом обновить целое число, чтобы отразить новое значение a[start - 1]?
• Может ли этот процесс быть повторенс a[end]?
• Если на самом деле значения a[start - 1] и a[end] могут быть отражены двумя целыми числами, разве весь префиксный массив больше не служит цели?Поэтому нельзя ли его удалить?

Без необходимости использовать префиксный массив и все зависимости хранилища от длины удаленного ввода, ваш алгоритм будет использовать постоянный объем памяти для достижения своей цели,тем самым делая это O (n) времени и O (1) пространства.

Я бы предпочел, чтобы вы решили это самостоятельно, основываясь на представленной выше информации, поскольку это домашняя работа.Тем не менее, я включил решение ниже для справки:

#include <iostream>
using namespace std;

void find( int *data, int &start, int &end )
{
    // reflects the prefix sum until start - 1
    int sumStart = 0;

    // reflects the prefix sum until end
    int sumEnd = 0;
    for( int i = start; i <= end; i++ )
        sumEnd += data[i];

    while( start < end )
    {
        int length = end - start + 1;
        int sum = 2 * ( sumEnd - sumStart );

        if( sum == length )
            break;
        else if( sum < length )
        {
            // sum needs to increase; get rid of the lower endpoint
            if( data[ start ] == 0 && data[ end ] == 1 )
            {
                // sumStart must be updated to reflect the new prefix sum
                sumStart += data[ start ];
                start++;
            }
            else
            {
                // sumEnd must be updated to reflect the new prefix sum
                sumEnd -= data[ end ];
                end--;
            }
        }
        else
        {
            // sum needs to decrease; get rid of the higher endpoint
            if( data[ start ] == 1 && data[ end ] == 0 )
            {
                // sumStart must be updated to reflect the new prefix sum
                sumStart += data[ start ];
                start++;
            }
            else
            {
                // sumEnd must be updated to reflect the new prefix sum
                sumEnd -= data[ end ];
                end--;
            }
        }
    }
}

int main() {
    int length;
    cin >> length;

    // get the data
    int data[length];
    for( int i = 0; i < length; i++ )
        cin >> data[i];

    // solve and print the solution
    int start = 0, end = length - 1;
    find( data, start, end );

    if( start == end )
        puts( "No soln" );
    else
        printf( "%d %d\n", start, end );

    return 0;
}

Answer 4

Как и Нил, я считаю полезным рассмотреть алфавит {± 1} вместо {0, 1}. Предположим, без ограничения общности, что по крайней мере столько же + 1 с, сколько -1 с. Следующий алгоритм, который использует O (sqrt (n log n)) бит и работает во времени O (n), связано с "AF"

Примечание: это решение не обманывает , предполагая, что ввод является изменяемым и / или имеет потерянные биты. На момент этого редактирования это решение было единственным, опубликованным с указанием времени O (n) и пространства o (n).

Более простая версия, которая использует O (n) битов, передает массив сумм префиксов и отмечает первое вхождение каждого значения. Затем он сканирует назад, рассматривая для каждой высоты от 0 до суммы (обр) максимальный подрешетку на этой высоте. Некоторая мысль показывает, что оптимум среди них (помните предположение). В Python:

sum = 0
min_so_far = 0
max_so_far = 0
is_first = [True] * (1 + len(arr))
for i, x in enumerate(arr):
    sum += x
    if sum < min_so_far:
        min_so_far = sum
    elif sum > max_so_far:
        max_so_far = sum
    else:
        is_first[1 + i] = False

sum_i = 0
i = 0
while sum_i != sum:
    sum_i += arr[i]
    i += 1
sum_j = sum
j = len(arr)
longest = j - i
for h in xrange(sum - 1, -1, -1):
    while sum_i != h or not is_first[i]:
        i -= 1
        sum_i -= arr[i]
    while sum_j != h:
        j -= 1
        sum_j -= arr[j]
    longest = max(longest, j - i)

Хитрость для уменьшения пространства заключается в том, что мы сканируем is_first последовательно, хотя и в обратном порядке относительно его конструкции. Поскольку переменные цикла помещаются в O (log n) битах, вместо is_first мы будем вычислять контрольную точку переменных цикла после каждого O (√ (n log n)) шагов. Это контрольные точки O (n / √ (n log n)) = O (√ (n / log n)), всего O (√ (n log n)) битов. Перезапуская цикл с контрольной точки, мы вычисляем по требованию каждый O (√ (n log n)) - битовый раздел is_first.

(PS: это может быть, а может и не быть моей ошибкой в том, что постановка задачи запрашивает пространство O (1). Я искренне извиняюсь, если я вытащил Fermat и предположил, что у меня есть решение проблемы гораздо сложнее, чем я думал.)

Answer 5

Этот алгоритм имеет O (n) время и O (1) пространство. Он может модифицировать исходный массив, но восстанавливает всю информацию обратно. Так что это не работает с массивами const. Если у этой головоломки есть несколько решений, этот алгоритм выбирает решение, ближайшее к началу массива. Или это может быть изменено, чтобы обеспечить все решения.

Алгоритм

Переменные:

• p1 - запуск подмассива
• p2 - конец подмассива

• d - разница 1 и 0 в подмассиве

  1. Рассчитать d, если d==0, остановить. Если d<0, инвертировать массив и после того, как найден сбалансированный подмассив, инвертировать его обратно.
  2. Пока d > 0 продвигается p2: если элемент массива равен 1, просто уменьшите как p2, так и d. В противном случае p2 должен передать подмассив формы 11*0, где * - некоторый сбалансированный подмассив. Чтобы сделать возможным возврат, 11*0? изменяется на 0?*00 (где ? - это значение рядом с подмассивом). Тогда d уменьшается.
  3. Магазин p1 и p2.
  4. Backtrack p2: если элемент массива равен 1, просто увеличить p2. В противном случае мы нашли элемент, измененный на шаге 2. Отменить изменения и передать подмассив формы 11*0.
  5. Advance p1: если элемент массива равен 1, просто увеличить p1. В противном случае p1 должен пройти подмассив формы 0*11.
  6. Хранить p1 и p2, если p2 - p1 улучшилось.
  7. Если p2 находится в конце массива, остановитесь. В противном случае перейдите к шагу 4.

Как это работает

Алгоритм перебирает все возможные позиции сбалансированного подмассива во входном массиве. Для каждой позиции подрешетки p1 и p2 располагаются как можно дальше друг от друга, обеспечивая локально самый длинный подмассив. Подмассив с максимальной длиной выбирается между всеми этими подмассивами.

Чтобы определить следующую лучшую позицию для p1, она переводится на первую позицию, где баланс между 1 и 0 изменяется на единицу. (Шаг 5).

Чтобы определить следующую лучшую позицию для p2, она продвигается к последней позиции, где баланс между 1 и 0 изменяется на единицу. Чтобы сделать это возможным, шаг 2 обнаруживает все такие позиции (начиная с конца массива) и модифицирует массив таким образом, что можно выполнять итерацию по этим позициям с помощью линейного поиска. (Шаг 4).

При выполнении шага 2 могут быть выполнены два возможных условия. Простой: когда найдено значение «1»; указатель p2 просто перемещается к следующему значению, особой обработки не требуется. Но когда значение '0' найдено, баланс движется в неправильном направлении, необходимо пройти через несколько битов, пока не будет найден правильный баланс. Все эти биты не представляют интереса для алгоритма, остановка p2 даст либо сбалансированный подмассив, который является слишком коротким, либо дисбалансированный подмассив. В результате, p2 должен пройти подмассив формы 11*0 (справа налево * означает любой сбалансированный подмассив). Там нет шансов пойти тем же путем в другом направлении. Но можно временно использовать некоторые биты из шаблона 11*0, чтобы разрешить возврат. Если мы изменим первое «1» на «0», второе «1» на значение рядом с крайним правым «0» и очистим значение рядом с крайним правым «0»: 11*0? -> 0?*00, тогда мы получим возможность ( во-первых) обратите внимание на шаблон на обратном пути, поскольку он начинается с «0», и (во-вторых) найдите следующую хорошую позицию для p2.

C ++ код:

#include <cstddef>
#include <bitset>

static const size_t N = 270;

void findLargestBalanced(std::bitset<N>& a, size_t& p1s, size_t& p2s)
{
    // Step 1
    size_t p1 = 0;
    size_t p2 = N;
    int d = 2 * a.count() - N;
    bool flip = false;

    if (d == 0) {
        p1s = 0;
        p2s = N;
        return;
    }

    if (d < 0) {
        flip = true;
        d = -d;
        a.flip();
    }

    // Step 2
    bool next = true;
    while (d > 0) {
        if (p2 < N) {
            next = a[p2];
        }

        --d;
        --p2;

        if (a[p2] == false) {
            if (p2+1 < N) {
                a[p2+1] = false;
            }

            int dd = 2;
            while (dd > 0) {
                dd += (a[--p2]? -1: 1);
            }

            a[p2+1] = next;
            a[p2] = false;
        }
    }

    // Step 3
    p2s = p2;
    p1s = p1;

    do {
        // Step 4
        if (a[p2] == false) {
            a[p2++] = true;
            bool nextToRestore = a[p2];
            a[p2++] = true;

            int dd = 2;
            while (dd > 0 && p2 < N) {
                dd += (a[p2++]? 1: -1);
            }

            if (dd == 0) {
                a[--p2] = nextToRestore;
            }
        }
        else {
            ++p2;
        }

        // Step 5
        if (a[p1++] == false) {
            int dd = 2;
            while (dd > 0) {
                dd += (a[p1++]? -1: 1);
            }
        }

        // Step 6
        if (p2 - p1 > p2s - p1s) {
            p2s = p2;
            p1s = p1;
        }
    } while (p2 < N);

    if (flip) {
        a.flip();
    }
}

Answer 6

Этот алгоритм работает за время O (n) и пространство O (1).

Использует простой трюк "сжимай, а затем расширяй". Комментарии в кодах.

public static void longestSubArrayWithSameZerosAndOnes() {
    // You are given an array of 1's and 0's only.
    // Find the longest subarray which contains equal number of 1's and 0's
    int[] A = new int[] {1, 0, 1, 1, 1, 0, 0,0,1};
    int num0 = 0, num1 = 0;

    // First, calculate how many 0s and 1s in the array
    for(int i = 0; i < A.length; i++) {
        if(A[i] == 0) {
            num0++;
        }
        else {
            num1++;
        }
    }
    if(num0 == 0 || num1 == 0) {
        System.out.println("The length of the sub-array is 0");
        return;
    }

    // Second, check the array to find a continuous "block" that has
    // the same number of 0s and 1s, starting from the HEAD and the
    // TAIL of the array, and moving the 2 "pointer" (HEAD and TAIL)
    // towards the CENTER of the array
    int start = 0, end = A.length - 1;
    while(num0 != num1 && start < end) {
        if(num1 > num0) {
            if(A[start] == 1) {
                num1--; start++;
            }
            else if(A[end] == 1) {
                num1--; end--;
            }
            else {
                num0--; start++;
                num0--; end--;
            }
        }
        else if(num1 < num0) {
            if(A[start] == 0) {
                num0--; start++;
            }
            else if(A[end] == 0) {
                num0--; end--;
            }
            else {
                num1--; start++;
                num1--; end--;
            }
        }
    }
    if(num0 == 0 || num1 == 0) {
        start = end;
        end++;
    }

    // Third, expand the continuous "block" just found at step #2 by
    // moving "HEAD" to head of the array and "TAIL" to the end of
    // the array, while still keeping the "block" balanced(containing
    // the same number of 0s and 1s
    while(0 < start && end < A.length - 1) {
        if(A[start - 1] == 0 && A[end + 1] == 0 || A[start - 1] == 1 && A[end + 1] == 1) {
            break;
        }
        start--;
        end++;
    }
    System.out.println("The length of the sub-array is " + (end - start + 1) + ", starting from #" + start + " to #" + end);

}

Answer 7

линейное время, постоянное пространство.Дайте мне знать, если есть какая-либо ошибка, которую я пропустил.
протестировано в python3.

def longestBalancedSubarray(A):
    lo,hi = 0,len(A)-1
    ones = sum(A);zeros = len(A) - ones
    while lo < hi:
        if ones == zeros: break
        else:
            if ones > zeros:
                if A[lo] == 1: lo+=1; ones-=1
                elif A[hi] == 1: hi+=1; ones-=1
                else: lo+=1; zeros -=1
            else:
                if A[lo] == 0: lo+=1; zeros-=1
                elif A[hi] == 0: hi+=1; zeros-=1
                else: lo+=1; ones -=1
    return(A[lo:hi+1])

Answer 8

Я бы сказал, что невозможно, чтобы алгоритм с O (1) существовал следующим образом. Предположим, вы повторяете ОДНАЖДЫ по каждому биту. Для этого требуется счетчик, которому нужно пространство O (log n). Возможно, можно утверждать, что n само является частью экземпляра задачи, тогда у вас есть длина ввода для двоичной строки длиной k: k + 2-log k. Независимо от того, как вы просматриваете их, вам нужна дополнительная переменная, на случай, если вам нужен индекс в этом массиве, который уже делает его не O (1).

Обычно у вас нет этой проблемы, потому что у вас есть проблема размера n, ввод n чисел размера log k, который складывается в nlog k. Здесь переменная длины log k равна просто O (1). Но здесь наш журнал k равен 1. Поэтому мы можем ввести только вспомогательную переменную, которая имеет постоянную длину (и я имею в виду действительно постоянную, она должна быть ограничена независимо от того, насколько велико n).

Здесь одна проблема - это описание проблемы. В компьютерной теории вы должны быть очень осторожны с кодировкой. Например. Вы можете сделать задачи NP полиномиальными, если переключитесь на унарное кодирование (потому что тогда входной размер будет экспоненциально больше, чем в n-арной (n> 1) кодировке.

Что касается n, то вход имеет размер 2-log n, нужно быть осторожным. Когда вы говорите в этом случае об O (n) - это действительно алгоритм, который является O (2 ^ n) (Это не тот вопрос, о котором мы должны обсуждать - потому что можно спорить, является ли само n частью описания или нет).

Answer 9

Вот решение ActionScript, которое выглядело так, как будто оно масштабировало O (n).Хотя это может быть больше похоже на O (n log n).Он определенно использует только O (1) памяти.

Предупреждение Я не проверил, насколько он завершен.Я мог пропустить некоторые дела.

protected function findLongest(array:Array, start:int = 0, end:int = -1):int {
    if (end < start) {
        end = array.length-1;
    }

    var startDiff:int = 0;
    var endDiff:int = 0;
    var diff:int = 0;
    var length:int = end-start;
    for (var i:int = 0; i <= length; i++) {
        if (array[i+start] == '1') {
            startDiff++;
        } else {
            startDiff--;
        }

        if (array[end-i] == '1') {
            endDiff++;
        } else {
            endDiff--;
        }

        //We can stop when there's no chance of equalizing anymore.
        if (Math.abs(startDiff) > length - i) {
            diff = endDiff;
            start = end - i;
            break;
        } else if (Math.abs(endDiff) > length - i) {
            diff = startDiff;
            end = i+start;
            break;
        }
    }

    var bit:String = diff > 0 ? '1': '0';
    var diffAdjustment:int = diff > 0 ? -1: 1;

    //Strip off the bad vars off the ends.
    while (diff != 0 && array[start] == bit) {
        start++;
        diff += diffAdjustment;
    }

    while(diff != 0 && array[end] == bit) {
        end--;
        diff += diffAdjustment;
    }

    //If we have equalized end. Otherwise recurse within the sub-array.
    if (diff == 0)
        return end-start+1;
    else
        return findLongest(array, start, end);      

}

Answer 10

Суммируйте все элементы в массиве, тогда diff = (array.length - sum) будет разницей в количестве 0 и 1.

1. Если diff равно array.length / 2, то максимальный подмассив = массив.
2. Если diff меньше, чем array.length / 2, тогда больше 1s, чем 0s.
3. Если diff больше, чем array.length / 2, тогда больше 0s, чем 1s.

Для случаев 2 и 3 инициализируйте два указателя, начало и конец указывают на начало и конец массива. Если у нас больше 1, то переместите указатели внутрь (start ++ или end--) в зависимости от того, будет ли array [start] = 1 или array [end] = 1, и обновите сумму соответствующим образом. На каждом шаге проверяйте sum = (end - start) / 2. Если это условие истинно, тогда start и end представляют границы вашего максимального подмассива.

Здесь мы заканчиваем тем, что делаем два прохода массива, один для вычисления суммы, и один, который перемещает указатели внутрь. И мы используем постоянное пространство, так как нам просто нужно хранить сумму и два значения индекса.

Если кто-то захочет сбить с толку какой-нибудь псевдокод, добро пожаловать :))