An algorithm for finding the longest sequence of the same element in an 1D array - finding the best solution

Question

I need to find an algorithm that will find the longest segment of an element in one dimensional array.

For example:

int[] myArr={1,1,1,3,4,5,5,5,5,5,3,3,4,3,3} 

the solution will be 5 because the sequnece of 5 is the longest. This is my solution to the problem:

static int findSequence(int [] arr, int arrLength){

    int frequency=1;
    int bestNumber=arr[0];
    int bestFrequency=0;

    for(int n=1;n<arrLength;n++){
        if(arr[n]!=arr[n-1]){ 
            if(frequency>bestFrequency){
                bestNumber=arr[n-1];
                bestFrequency=frequency;
            }
            frequency=1;
        }else { 
            frequency++;
        }
    }

    if( frequency>bestFrequency){
        bestNumber=arr[arrLength-1];
        bestFrequency=frequency;
    }

    return bestNumber;
}

but I am not satisfied. Maybe someone knows a more effective solution?

Answer 1

You can skip some number in the array in the following pattern:

jump_count ( /2). 2 . jump_count bestFrequency.

,

• <= jump_count, , .

  . 2 2 2 2 3 3 = 0 ( ), , 3 = 2

• > jump_count, , , , bestFrequency.

  . 2 2 2 2 2 3 3 = 1 ( ), 2 = 1 + 4 < bestFrequency, , 3 = 2.

• = , , , . , + jump_count, , 2.

  :

  a) 2 2 2 2 2 2 ( ), , 2. , jump_count .

  b) 2 2 2 2 3 2 ( ), , 2. , 2. , 2 = 1 + 4. < bestFrequency, , 2 ( ) = 1.

. .

P.S. , , .

Answer 2

:

public static void longestSequence(int[] a) {
    int count = 1, max = 1;

    for (int i = 1; i < a.length; i++) {
        if (a[i] == a[i - 1]) {
            count++;
        } else {
            if (count > max) {
                max = count;
            }
            count = 1;
        }
    }

    if (count> max)
        System.out.println(count);
            else
        System.out.println(max);    
}

Answer 3

.

( ) . O (n), , , , .

- bestFrequency n+bestFrequency > arrayLength, . , , .

Answer 4

, , :

for(int n=1;n<arrLength && frequency + (arrLength - n) >= bestFrequency;n++){

- , (, , ).

, , O (n) n - .

Answer 5

, O (n), , , O (log n), ( , , @BlackJack , ):

- , ( , , ). ( ). , . , . , , .

- , , . , , . , .

I think this is still an O (n) algorithm, because a decent case is still looking for every single element (count the maximum length of 1 or 2). But you are limited to checking each element once, and first do a search in the most probable longest branches (based on start / middle / end matches), this can potentially skip some fairly long runs. A search in width, not in depth, will also help.