finding longest sequence of a particular value

I wa开发者_Python百科nt to find the longest sequence of a particular number i.e. 1 appearing in an array. Suppose the array is {1,0,0,0,1,1,1,1,0,0,1,1}; the answer should be 4 as one appears at most four times consecutively.

---

Use run length encoding.

In R, it's just

max(rle(x)$lengths)

---

Start with an array of numbers, A, find the longest contiguous run of some number N in A.

Pseudo 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 is the answer

The idea is that once you find a contiguous run of N's you can jump ahead at least that far in the array before checking for another candidate.

This algorithm has a possible sublinear run time because of the jump factor. Worst case is that every A[i] will be examined.

---

There will be more efficient methods, but this is what i got for now (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;
                }
            }

---

A = array, L = its length

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

---

Here is another linear solution, idea is to maintain two runners. On the beginning boundary of 1 the 1st runner waits until 2nd runner has reached the end (i.e 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 is answer.