Finding the longest sequence of increasing numbers in an array

Question

A continuation of this queston. The task's description can also be found there.

After reformatting the code and getting rid of the ArrayIndexOutOfBounds check,it now looks like this:

public static List<Integer> findLongestIncreasingSequence(int[] numbersToBeProcessed) {

        if (numbersToBeProcessed.length == 0) {
            return null;
        }

        List<Integer> longestIncreasingSequence = new ArrayList<Integer>();
        List<Integer> currentNumbersSequence = new ArrayList<Integer>();

        // the first number will be added always,no matter what
        currentNumbersSequence.add(numbersToBeProcessed[0]);

        for (int i = 1; i < numbersToBeProcessed.length; i++) {

            int currentNumber = numbersToBeProcessed[i];
            int previousNumber = numbersToBeProcessed[i - 1];

            if (currentNumber > previousNumber) {
                currentNumbersSequence.add(currentNumber);
            } else {
                // checks if the current sequence is bigger
                if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
                    longestIncreasingSequence.clear();
                    longestIncreasingSequence.addAll(currentNumbersSequence);
                }
                // clear the current sequence so it can start all over again
                currentNumbersSequence.clear();
                // after clearing add the current number as the first of the new
                // sequence
                currentNumbersSequence.add(currentNumber);
            }
        }
        // at the end of the loop always compare the two sequences.
        if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
            longestIncreasingSequence.clear();
            longestIncreasingSequence.addAll(currentNumbersSequence);
        }
        return longestIncreasingSequence;
    }

There are couple of things that bother me about the algorithm above:

1. We never actually check the n-1 number at the start of the algorithm - instead we directly check if the n number and we process it. This is why I have added the currentNumbersSequence.add(numbersToBeProcessed[0]); code line before we go in the for loop.

2. What if the last n number is bigger than n-1? That means that we do not go into the else statement and the current sequence will never be compared against the largest one at this moment. This is why I had to add an extra check after the for loop. However it leads to a very obvious code repetition.

Answer 1

No need for temporary lists

In your last review, it was mentioned that you could just use two integers to keep track of the sequences instead of two whole lists. So instead of currentNumbersSequence and longestIncreasingSequence, you could track just the start and length of those two sequences. The code then becomes:

public static List<Integer> findLongestIncreasingSequence(int[] numbersToBeProcessed) {

    if (numbersToBeProcessed.length == 0) {
        return null;
    }

    int bestStart  = 0;
    int curStart   = 0;
    int bestLength = 1;
    int curLength  = 1;

    for (int i = 1; i < numbersToBeProcessed.length; i++) {
        if (numbersToBeProcessed[i] > numbersToBeProcessed[i-1]) {
            curLength++;
            if (curLength > bestLength) {
                bestStart  = curStart;
                bestLength = curLength;
            }
        } else {
            curStart  = i;
            curLength = 1;
        }
    }
    ArrayList<Integer> ret = new ArrayList<>(bestLength);
    for (int i = 0; i < bestLength; i++) {
        ret.add(numbersToBeProcessed[bestStart+i]);
    }
    return ret;
}

Answer 2

You actually have to pieces of code that are repeated:

if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
    longestIncreasingSequence.clear();
    longestIncreasingSequence.addAll(currentNumbersSequence);
}

and

currentNumbersSequence.add(currentNumber);

The former should be extracted and put into a method or just return the longest sequence if you're out of the loop (and this takes care of your concern #2). The latter can just be taken out of the if condition. The code inside the for loop can be written as follows:

        int currentNumber = numbersToBeProcessed[i];
        int previousNumber = numbersToBeProcessed[i - 1];

        if (currentNumber <= previousNumber) {
            // replace this piece with the call to the method that I suggested previously
            if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
                longestIncreasingSequence.clear();
                longestIncreasingSequence.addAll(currentNumbersSequence);
            }
            currentNumbersSequence.clear();
        }

        currentNumbersSequence.add(currentNumber);

For you 1st concern you could change your for loop into the following:

    for (int i = 0; i < numbersToBeProcessed.length - 1; i++) {

        int currentNumber = numbersToBeProcessed[i + 1];
        int previousNumber = numbersToBeProcessed[i];
        currentNumbersSequence.add(previousNumber);

        // rest of the code

        // you should also remove the 'currentNumbersSequence.add(currentNumber);' line
    }

This change allows you to remove the currentNumbersSequence.add(numbersToBeProcessed[0]); line.

So, in short, the method should become something like the following (not tested):

public static List<Integer> findLongestIncreasingSequence(int[] numbersToBeProcessed) {
    if (numbersToBeProcessed.length == 0) {
        return null;
    }

    List<Integer> longestIncreasingSequence = new ArrayList<Integer>();
    List<Integer> currentNumbersSequence = new ArrayList<Integer>();

    for (int i = 0; i < numbersToBeProcessed.length - 1; i++) {

        int currentNumber = numbersToBeProcessed[i];
        int previousNumber = numbersToBeProcessed[i - 1];
        currentNumbersSequence.add(previousNumber);

        if (currentNumber <= previousNumber) {
            // checks if the current sequence is bigger
            if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
                longestIncreasingSequence.clear();
                longestIncreasingSequence.addAll(currentNumbersSequence);
            }
            // clear the current sequence so it can start all over again
            currentNumbersSequence.clear();
        }
    }
    // at the end of the loop always compare the two sequences.
    if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
        return currentNumbersSequence;
    }
    return longestIncreasingSequence;
}