найти самую длинную последовательность определенного значения

Question

Я хочу найти самую длинную последовательность определенного числа, то есть 1, появляющуюся в массиве. Предположим, что массив равен {1,0,0,0,1,1,1,1,0,0,1,1}; ответ должен быть 4, так как один появляется не более четырех раз подряд.

Answer 1

Использовать кодирование длины серии .

В R , это просто

max(rle(x)$lengths)

Answer 2

Начните с массива чисел, A, найдите самое длинное непрерывный пробег некоторого числа N в A.

Псевдо C ...

MaxRun = 0 /* Longest run so far */
for (i = 0; i < length(A);) {
  if A[i] = N {
    /* Potential run of N's... */

    /* Scan backward for first N in run */
    for (j = i; j > 0 & A[j-1] = N; j--);

    /* Scan forward to last N in run */
    for (k = i; k < length(A)-1 & A[k+1] = N; k++);

    /* Check to see if longer run found... */
    if (k-j+1 > MaxRun) then MaxRun = k-j+1;

    i = k /* jump i to last N found */
  }
  i = i + MaxRun + 1 /* Jump by longest run plus 1 */
}

MaxRun - это ответ

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

Этот алгоритм имеет возможное сублинейное время выполнения из-за коэффициента скачка. В худшем случае каждый A [i] будет проверен.

Answer 3

Будут более эффективные методы, но это то, что я получил сейчас (C#):

            int count = 0;
            int maxCount = 0;

            for (int i = 0; i < someArray.Count(); i++)
            {
                if (someArray[i] == 1)
                {
                    count++;
                }
                else
                {
                    if(count > maxCount)
                    {
                        maxCount = count;
                    }

                    count = 0;
                }
            }

Answer 4

Вот еще одно линейное решение, идея состоит в том, чтобы поддерживать двух бегунов.На границе начала 1 1-й бегун ждет, пока 2-й бегун не достиг конца (т. Е. 0).

int i = 0, j= 0, max = 0, n = A.length;

while ( j < n ) {

  if (j == (n-1)) { // reached boundary

    j = ( A[j] == 1) ? j++ : j;
    int k = j-i;
    if ( k > max ) { max = k;} 
  }

  else if ( A[j] == 1 ) { j++; }// increment 2nd runner

  else { 

    int k = j-i;
    if ( k > max ) { max = k;}
    j++; i = j;
  }
}

max - это ответ.

Answer 5

A = массив, L = его длина

cnt = 0
max = 0
for i = 0 .. L - 1
  if A[i] == 0
    if (cnt > max) max = cnt
    cnt = 0
  else
    cnt = cnt + 1
if (cnt > max) max = cnt