finding longest sequence of consecutive numbers

Question

Problem H (Longest Natural Successors):

Two consecutive integers are natural successors if the second is the successor of the first in the sequence of natural numbers (1 and 2 are natural successors). Write a program that reads a number N followed by N integers, and then prints the length of the longest sequence of consecutive natural successors.

Example:

Input 7 2 3 5 6 7 9 10 Output 3 this is my code so far and i have no idea why it does not work

import java.util.Scanner;

public class Conse {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        int[] array = new int[x];
        for (int i = 0; i < array.length; i++) {
            array[i] = scan.nextInt();
        }
        System.out.println(array(array));

    }

    public static int array(int[] array) {
        int count = 0, temp = 0;
        for (int i = 0; i < array.length; i++) {
            count = 0;
            for (int j = i, k = i + 1; j < array.length - 1; j++, k++) {
                if (Math.abs(array[j] - array[k]) == 1) {
                    count++;
                } else {
                    if (temp <= count) {
                        temp = count;
                    }
                    break;
                }
            }
        }
        return temp + 1;
    }

}

Answer 1

I'm not sure I understand this question correctly. The answer's written here assumes that the the natural successors occur contiguously. But if this is not the same then the solution here might not give the correct answer.

Suppose instead of [7 2 3 5 6 7 9 10] the input was [7 2 6 3 7 5 6 9 10] then the answer becomes 2 while the natural successor [5 6 7] is present in the array.

If the input is not sorted we'll have to use a different approach. Like using HashSet

1. Load the entire array into a HashSet which removes duplicates.
2. Pick the first value from the HashSet and assigned it to start and end and remove it from the set.
3. Now decrements start and check if it is present in the HashSet and continue till a particular value for start is not present int the HashSetwhile removing the value being searched from the set.
4. Do the same for end except that you will have to increase the value of end for each iteration.
5. We now have to continuous range from start to end present in the set and whose range is current_Max = end - start + 1
6. In each iteration we keep track of this current_Max to arrive at the longest natural successor for the entire array.

And since HashSet supports Add, Remove, Update in O(1) time. This algorithm will run in O(n) time, where n is the length of the input array. The code for this approach in C# can be found here

Answer 2

Since your question has "Problem H" associated with it, I'm assuming you are just learning. Simpler is always better, so it usually pays to break it down into "what has to be done" before starting on a particular road by writing code that approaches the problem with "how can this be done."

In this case, you may be over-complicating things with arrays. A number is a natural successor if it is one greater than the previous number. If this is true, increment the count of the current sequence. If not, we're starting a new sequence. If the current sequence length is greater than the maximum sequence length we've seen, set the max sequence length to the current sequence length. No arrays needed - you only need to compare two numbers (current and last numbers read).

For example:

public static void main(String[] args) {
 Scanner scan = new Scanner(System.in); 

 int N = scan.nextInt();

 int maxSequenceLen = 0;  // longest sequence ever
 int curSequenceLen = 0;  // when starting new sequence, reset to 1 (count the reset #)
 int last = 0;

 for(int i = 0; i < N; i++) {
     int cur = scan.nextInt();
     if ((last+1) == cur){
         ++curSequenceLen;
     }
     else{
         curSequenceLen = 1;
     }
     if (curSequenceLen > maxSequenceLen){
         maxSequenceLen = curSequenceLen;
     }
     last = cur;
 }
 System.out.println(maxSequenceLen);

Caveat: I'm answering this on a computer that does not have my Java development environment on it, so the code is untested.

Answer 3

This seems to work:

public static int longestConsecutive(int[] array) {
    int longest = 0;
    // For each possible start
    for (int i = 0; i < array.length; i++) {
        // Count consecutive.
        for (int j = i + 1; j < array.length; j++) {
            // This one consecutive to last?
            if (Math.abs(array[j] - array[j - 1]) == 1) {
                // Is it longer?
                if (j - i > longest) {
                    // Yup! Remember it.
                    longest = j - i;
                }

            } else {
                // Start again.
                break;
            }
        }
    }
    return longest + 1;
}

public void test() {
    int[] a = new int[]{7, 2, 3, 5, 6, 7, 9, 10};
    System.out.println("Longest: " + Arrays.toString(a) + "=" + longestConsecutive(a));
}

prints

Longest: [7, 2, 3, 5, 6, 7, 9, 10]=3

Answer 4

Why two loops? What about

public static int array(final int[] array) {
    int lastNo = -100;
    int maxConsecutiveNumbers = 0;
    int currentConsecutiveNumbers = 0;

    for (int i = 0; i < array.length; i++) {
        if (array[i] == lastNo + 1) {
            currentConsecutiveNumbers++;
            maxConsecutiveNumbers = Math.max(maxConsecutiveNumbers,
                    currentConsecutiveNumbers);
        } else {
            currentConsecutiveNumbers = 1;
        }
        lastNo = array[i];
    }
    return Math.max(maxConsecutiveNumbers, currentConsecutiveNumbers);
}