I want to find the longest sequence of a given number in an array. For example,

Given:

int number = 5;
int[] array = new int[]{5,5,1,1,1,1,5,5,5,1,2};

This should print 3 since 5,5,5 is the longest sequence of 5s. But if the number was 1, it would print 4.

I came up with:

    int count = 0;
    int max = 0;
    for (int i = 0; i < array.length; i  ) {
        if (array[i] == number) {
            count  ;
        } else {
            if (count > max) {
                max = count;
                count = 0;
            }
        }
    }
    if (count > max) {
        max = count;
    }
    System.out.println(max);

But this doesn't work if int number = 0 and the array is {10,3,0,0,2,6,7,2,0,2,-1,-3,0,0,0,0,0,2,-3,-4,-5,0,0,0,0}

It prints 6 instead of 5.

What am I missing?

CodePudding user response：

As others have said, you need to check the max every time around the loop and reset the count to zero whenever the number doesn't match. I think you can simplify your logic somewhat by checking for a new maximum right after incrementing the count, and using an enhanced for loop.

int count = 0;
int max = 0;
for (int x : array) {
    if (x == number) {
        count  ;
        if (count > max) {
            max = count;  // a new maximum has been achieved 
        }
    } else {
        count = 0;  // the number does not match
    }
}
System.out.println(max);

CodePudding user response：

The problem arises if the array first includes a sequence of the wanted number of length x, then a sequence of the wanted number of length y < x and then the longest sequence of wanted number of length z. The relevant part is the sequence of length y < x.

Since y < x, the statement if (count > max) is false. Hence, count = 0; is not executed and count is still on y.

Then, when the code starts increasing the count again for the longest sequence, it keeps increasing count, which is y, but should be 0. Therefore, the final count is y z, where it should only be z.

For the array provided, we can see that x = 2, y = 1 and z = 5:

{10,3,0,0,2,6,7,2,0,2,-1,-3,0,0,0,0,0,2,-3,-4,-5,0,0,0,0} 
     | x |       |y|       |    z    | 
    

The fix is to move count out of the if, into the else:

        ...
        } else {
            if (count > max) {
                max = count;
            }
            count = 0;
        }
        ...

Ideone demo

CodePudding user response：

To count the length of the sequence inside an array, the main loop should be split in two parts:

• skip all the numbers which are NOT equal to number
• count the length of sequence until the first non-number element is detected or end of array occurs whichever comes first

static int lengthOfLongest(int number, int ... array) {
    int max = 0;
    for (int i = 0; i < array.length; i  ) {
        int count = 0;
        while (i < array.length && array[i] != number) i  ; // skip
        for (int j = i; j < array.length && array[j] == number; j  , i  ) {
            count  ;
        }
        System.out.println("lost at "   i   "; count = "   count);
        if (count > max) {
            max = count;
        }
    }
    System.out.println(max);    
    return max;
}

Test:

lengthOfLongest(0,
    10,3,0,0,2,6,7,2,0,2,-1,-3,0,0,0,0,0,2,-3,-4,-5,0,0,0,0
);

Output (with debug logs)

found at 2
lost at 4; count = 2
found at 8
lost at 9; count = 1
found at 12
lost at 17; count = 5
found at 21
lost at 25; count = 4
5

CodePudding user response：

You can start by sorting your array, then use a HashMap to count the sequence:

int[] array = new int[]{5, 5, 1, 1, 1, 1, 5, 5, 5, 1, 2};
var length = array.length;


// sort the array
do {
    for (int i = 0; i < array.length - 1; i  ) {
        var temp = array[i];
        if (array[i] > array[i   1]) {
            array[i] = array[i   1];
            array[i   1] = temp;
        }
    }
    length--;
} while (length != 0);

// print the array after sorting
System.out.println(Arrays.toString(array));

//calculate the sequence of each element and store it in a HashMap
HashMap<Integer,Integer> result = new HashMap<>();

for (int j : array) {
    var count = 0;
    for (int k : array) {
        if (k == j) {
            count  ;
        }
    }
    result.put(j, count);
}
System.out.println(result);

Finally you use a simple stream operation to get the max sequence:

//retrieve the max sequence
final Optional<Integer> max = result.values().stream().max(Comparator.naturalOrder());
max.ifPresent(integer -> System.out.println("max number is "   integer));

Console:

[1, 1, 1, 1, 1, 2, 5, 5, 5, 5, 5]
{1=5, 2=1, 5=5}
max number is 5

Java version used : 16.

CodePudding user response：

Try this.

static int longestSequence(int[] array) {
    int length = array.length;
    if (length == 0)
        return 0;
    int max = 1, prev = array[0], count = 1;
    for (int i = 1; i < length; prev = array[i],   i)
        if (array[i] != prev)
            count = 1;
        else if (  count > max)
            max = count;
    return max;
}

public static void main(String[] args) {
    int[] array = { 10, 3, 0, 0, 2, 6, 7, 2, 0, 2, -1, -3, 0, 0, 0, 0, 0, 2, -3, -4, -5, 0, 0, 0, 0 };
    System.out.println(longestSequence(array));
}

output:

5